import javax.print.attribute.EnumSyntax;
import javax.swing.*;
import javax.swing.plaf.metal.MetalTheme;
import java.awt.event.MouseAdapter;
import java.io.*;
import java.lang.reflect.Array;
import java.time.chrono.MinguoChronology;
import java.util.*;
import java.util.concurrent.Callable;



class fat {
    public    int a = 0;

    void run() {

    }
}

class chlid extends fat {

    public chlid() {
        super();
    }

    void t() {
        super.run();
        int a = super.a;
        System.out.println(a);
    }

    void run() {
        System.out.println(11);
    }

    public    void main(String[] args) {
        chlid c = new chlid();
        c.t();
    }
}
/**
 * 并查集
 */
class unionFind {

    //每个下标对应的就是一个节点
    private int[] arr;
    private int size;

    public unionFind(int size) {
        arr = new int[size];
        Arrays.fill(arr, -1);//初始化为-1
        this.size = size;
    }

    //s->e 将s储存e的下标
    public void add(int s, int e) {
        //s有可能是另一个集合中的，那么这是其实是将这个集合的根节点来和e合并的
        s = getRoot(s);
        e = getRoot(e);
        if (s == e) {//是同一个集合中的
            return;
        }
        //将这个最终的根加上合并的根的总和
        arr[e] = arr[e]+arr[s];
        //把根s并入e这个集合中
        arr[s] = e;
    }

    //获得节点对应的根节点,小于0的是根节点
    int getRoot(int x) {
        while (arr[x] >= 0) {
            x = arr[x];
        }
        return x;
    }

    int getUnion() {
        int ret = 0;
        for (int i = 0; i < size; i++) {
            if (arr[i] < 0) {
                ret++;
            }
        }
        return ret;
    }
}
/**
 * 快读 System.in 是字节流OutputStreamWriter是将字节流转换为字符流
 * BufferedWriter是创建一个缓冲区，一次io全部读完数据储存在内存缓冲区
 * PrintWriter是将这个缓存包装，方便使用，这里的方法就和System.out一样
 * public    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */

//快读
class Read {
    //字符粗裁接 拿到bf缓冲区中的数据 通过空格将数据裁剪为一个一个的字符串
    StringTokenizer st = new StringTokenizer("");

    //字节流-》字符流，再创建一个内存缓冲区，将所有数据读到里面
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    //每次读一次就返回一个字符串 被空格分开的
    String next() throws IOException {

        while (!st.hasMoreTokens()) {
            //表示是否还有字符串再st中 若没有就再读取
            st = new StringTokenizer(bf.readLine());
        }

        return st.nextToken();//放回一段
    }

    public String readLine() throws Exception { //  不推荐使用
        //读一行直接返回
        return bf.readLine();
    }

    public int nextInt() throws Exception {
        //调用next读一个字符串 用空格分开的
        return Integer.parseInt(next());
    }

    public long nextLong() throws Exception{
        return Long.parseLong(next());
    }

    public Double nextDouble() throws Exception{
        return Double.parseDouble(next());
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//
//public class ListNode {
//    int val;
//    ListNode next = null;
//    public ListNode(int val) {
//      this.val = val;
//    }
//  }
class myMap{
    ArrayList<Character> chars = new ArrayList<>();
    ArrayList<Integer> count = new ArrayList<>();//char对应的下标来储存数量
    int MaxCount = 0;
    public void put(char c) {
        if (!chars.contains(c)) {
            chars.add(c);
            count.add(1);
        } else {//存在这个char
            int i = getCIn(c);
            count.set(i, count.get(i) + 1);
            MaxCount = Math.max(MaxCount, count.get(i));
        }
    }

    public int getCIn(char c) {
        for (int i = 0; i < chars.size(); i++) {
            if (chars.get(i) == c) {
                return i;
            }
        }
        return -1;
    }

    public char[] getChars() {
        char[] ret = new char[chars.size()];
        for (int i = 0; i < chars.size(); i++) {
            ret[i] = chars.get(i);
        }
        return ret;
    }

    public int[] getCount() {
        int[] ret = new int[count.size()];
        for (int i = 0; i < count.size(); i++) {
            ret[i] = count.get(i);
        }
        return ret;
    }

    public int getMaxCount() {
        return MaxCount;
    }
}

class comIndex implements Comparator<Integer> {
    int[] arr;

    public comIndex(int[] ints) {
        arr = ints;
    }
    @Override
    public int compare(Integer o1, Integer o2) {
        return arr[o1] - arr[o2];
    }
}
class ListN{
    int val;
    ListN next;

    public ListN(int val) {
        this.val = val;
    }
}

enum A{
    red(1), blue(2);

    A(int a) {

    }
}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

class big implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 - o2;
    }
}

/**
 * TinyUrl 的加密和解密
 * 搞一个hashMap，encode来随机生成一个key 其中储存这个longUrl，在返回这个key
 */
class TinyUrl {
    HashMap<String, String> https = new HashMap<>();

    // Encodes a URL to a shortened URL. 加密
    public String encode(String longUrl) {
        String retUrl = "http://tinyurl.com";
        Random random = new Random();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 5; i++) {
            sb.append((char)i);
        }
        retUrl = retUrl + "/" +sb.toString();
        https.put(retUrl, longUrl);

        return retUrl;
    }

    // Decodes a shortened URL to its original URL. 解密
    public String decode(String shortUrl) {
        return https.get(shortUrl);
    }
}

class mainRun {



    /**
     * 根据身高重建队列
     * people[i]表示的是一个学生，people[i][0]表示这个学生的身高，people[i][1]表示这个学生前面有多少个比他高或者相同的
     * 对这个数组排序，使people[i][1]表示的信息正确
     * 因为p[1]表示的是前面有多少个人的身高大于等于他的，那么我将数组按照降序排序，在从左往右一次放入，放到i这个位置的ren人他身高一定是
     * 小于等于前面放入的人的，那么在根据他的p[1]的条件来给他找到对应的位置
     */
    public int[][] reconstructQueue(int[][] people) {
        int n = people.length;
        List<int[]> list = new ArrayList<>(n);
        //降序
        Arrays.sort(people, (i, j) -> {
            return j[0] - i[0] == 0 ? i[1] - j[1] : j[0] - i[0];
        });
        //因为有0在那么，i[1]就是在i这里
        list.add(people[0]);
        for (int i = 1; i < n; i++) {
            list.add(people[i][1], people[i]);
        }

        return list.toArray(new int[n][2]);
    }

    //{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}
    public void mainrecon(String[] args) {
        int[][] ints = reconstructQueue(new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}});

    }

    /**
     * 雪糕的最大数量
     * costs[i]表示的是第i个位置的价格，coins表示的是拥有的硬币数，返回嫩买到的额最多的雪糕数
     * 贪心，每次买最便宜的就好，规定使用计算排序解决
     * 搞一个HashMap记录每个数字出现的次数，在从小到大输出就好
     */
    public int maxIceCream(int[] costs, int coins) {
        int[] count = new int[100001];
        for (int i : costs) {
            count[i]++;//i这个价格的雪糕的数量
        }
        int ret = 0;
        for (int i = 0; i < count.length; i++) {
            if (coins >= i * count[i]) {//买下所有
                ret += count[i];
                coins -= i * count[i];
            } else {//买下部分
                int buyC = coins / i;
                ret += buyC;
                return ret;
            }
        }
        return 0;
    }

    public void mainmaxI(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        Random random = new Random();
        for (int i = 50; i >= 1; i--) {
            int j = random.nextInt(100);
            map.put(j, i);
        }

    }

    /**
     * n 的第 k 个因子
     * 如果n%i==0 那么i就时n的因子，并对因子进行升序排序，返回第k大的因子
     * topK问题，搞个大根堆堆顶的就是第k大的因子
     */
    public int kthFactor(int n, int k) {
        PriorityQueue<Integer> heapBig = new PriorityQueue<>((a, b) -> b - a);

        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                heapBig.add(i);
                if (heapBig.size() == k) {
                    return heapBig.poll();
                }
            }
        }
        return -1;
    }

    /**
     * 使括号有效的最少添加
     * 栈 如果是左括号就入栈，右括号就出栈，如果右括号还有，而栈为空，count++，最后返回count + 栈的大小
     */
    public int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    count++;
                }
            }
        }
        return count + stack.size();
    }

    /**
     * 字符大小写全排列
     * 给一个字符串，通过将他的每个字符转换为大小写来得到不同的字符串，返回这些所有可能的字符串
     * 动态规划 将字符串变为数组储存，对于每个位置的字符都有变和不变俩种选择 dp[i]代表的是到这个位置的字符串的所有可能
     * dp[i] = dp[i]变+dp[i-1] +dp[i]不变 +dp[i-1]
     * ab
     * a A 1
     * aB aB,Ab,ab 2
     * StringBuffer 有个方法叫做setCharAt 可以直接修改指定位置的字符为另一个字符
     * 可以改为递归
     */
    public List<String> letterCasePermutation(String s) {
        List<List<String>> dp = new LinkedList<>();
        char[] chars = s.toCharArray();
        int n = chars.length;
        //初始一个防止越界
        List<String> init = new LinkedList<>();
        init.add("");
        dp.add(init);//防止越界

        for (int i = 1; i <= n; i++) {
            char c = chars[i - 1];
            //是数字就没有大小写
            if (Character.isDigit(c)) {
                List<String> list = new LinkedList<>();
                List<String> tmp = dp.get(i - 1);
                //将字符插入到末尾 遍历tmp
                for (int k = 0; k < tmp.size(); k++) {
                    list.add(tmp.get(k) + c);
                }
                dp.add(list);
                continue;
            }
            //这个会加入到dp中
            List<String> list = new LinkedList<>();
            //获得大小写
            char cToLower = Character.toLowerCase(c);
            char cToUpper = Character.toUpperCase(c);
            char[] charsLU = {cToLower, cToUpper};

            //循环遍历i-1这个链表中的字符串并加上c在加入到list中
            for (int j = 0; j < 2; j++) {
                List<String> tmp = dp.get(i - 1);
                //将字符插入到末尾 遍历tmp
                for (int k = 0; k < tmp.size(); k++) {
                    list.add(tmp.get(k) + charsLU[j]);
                }
            }
            dp.add(list);
        }
        return dp.get(n);
    }

    public void mainLetter(String[] args) {
        StringBuilder sb = new StringBuilder("111");
        sb.setCharAt(1, 'a');
        System.out.println(sb.toString());
        letterCasePermutation("ab");
    }

    /**
     * 根据字符串的评率排序
     * 定义一个数组，大小为75的数组 '0'==48 'z' = 122
     * 这样下标0表示的是0+‘0’的ascll码值 74+48 = 122
     * 对这个数组排序，值为0的不答打印，值不为零的打印，从后往前打印,使用下标排序
     */
    public String frequencySort(String s) {
        int n = s.length();
        int[] freq = new int[75];
        Integer[] index = new Integer[75];
        for (int i = 0; i < index.length; i++) {
            index[i] = i;
        }

        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            freq[c - '0']++;
        }

        Arrays.sort(index, (Integer i, Integer j) -> {
            return freq[i] - freq[j];
        });
        StringBuilder sb = new StringBuilder();


        for (int i = index.length - 1; i >= 0; i--) {
            if (freq[index[i]] == 0) {
                break;
            }
            for (int j = 0; j < freq[index[i]]; j++) {
                sb.append((char) (index[i] + '0'));
            }
        }

        return sb.toString();
    }

    public void mainFREQ(String[] args) {
        System.out.println(frequencySort("111223"));
//        System.out.println(Character.isLetter('c'));
//        //范围是48 - 122
//        System.out.printf("%03d\n",(int)'0');
//        System.out.printf("%03d\n",(int)'9');
//        System.out.printf("%03d\n",(int)'A');
//        System.out.printf("%03d\n",(int)'Z');
//        System.out.printf("%03d\n",(int)'a');
//        System.out.printf("%03d\n",(int)'z');
    }

    /**
     * 只出现了一次的元素II
     * 其他均出现了3次就一个出现了1次，找到这个一次的元素
     * 0,1,0,1,0,1,99
     * hashmap<int,boolean>
     * a & a == 0
     */
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
            if (map.get(i) == 3) {
                map.remove(i);
            }
        }
        Set<Integer> set = map.keySet();
        for (Integer i : set) {
            return i;
        }
        return 0;
    }

    /**
     * 设计机械累加
     * 这时一个只能进行加法的程序
     * 逻辑运算符短路
     */
    public int mechanicalAccumulator(int target) {
        //逻辑运算符短路 a&&b如果a之后结果能过确定也就是为false，那么就不会运算b中的答案
        // 那么就可以使用这个性质决定函数递归的出口
        boolean flg = (target <= 0) && (target += mechanicalAccumulator(target - 1)) > 0;
        return target;
    }

    /**
     * 打家劫舍 动态规划
     * 不能拿连续俩个屋子中的金额，不然会报警
     * 1,2,3,1
     * 对于dp[i]有俩种情况 dp[i] = dp[i-2]+nums[i]拿这家的,dp[i-1]不拿这家的
     * dp 0 0 1 2 4 4
     * 2,7,9,3,1
     * dp 0 0 2 7 11 11 12
     */
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 2];//防止越界
        for (int i = 2; i < nums.length + 2; i++) {//6
            dp[i] = Math.max(dp[i - 2] + nums[i - 2], dp[i - 1]);
        }
        return dp[nums.length + 1];
    }


    /**
     * 三角形的最小路径和
     * 给一个由数字组成的三角形的，返回从顶到尾巴的最小的路径和
     * 和二叉树的遍历很像，我需要先知道在这个三角形中如何知道自己对应的左右支点在哪里就好
     * 对于arr[y][x]的节点 他的左节点为arr[y+1][x],右节点为arr[y+1][x+1]
     * 写一个中序遍历
     */


    int[][] dp;

    public int minimumTotal(List<List<Integer>> triangle) {
        triangleY = triangle.size();
        dp = new int[triangleY + 1][triangleY + 1];
        minimumTotalRecursion(triangle, triangleY - 1);//从尾巴开始
        return dp[0][0];
    }

    /**
     * 动态规划 从下往上 那么dp[i][j] 就表示以这个位置向下的最小的路径和
     * dp[i][j] = Math.min(dp[i+1][j]+dp[i][j+1])+dp[i][j]
     */
    private void minimumTotalRecursion(List<List<Integer>> triangle, int y) {
        if (y == -1) {
            return;
        }
        List<Integer> list1 = triangle.get(y);
        for (int i = 0; i < triangle.get(y).size(); i++) {
            //左边最小加右边最小加当前的这个
            dp[y][i] = Math.min(dp[y + 1][i], dp[y + 1][i + 1]) + list1.get(i);
        }
        minimumTotalRecursion(triangle, y - 1);
    }


    //overtime fk so beautiful code!  时间复杂度O(2^n)
    //会改记得改下ollama的模型路径
    int triangleY = 0;
    int minTriangle = Integer.MAX_VALUE;
    int pathValue = 0;

    private void minimumTotalRecursionOverTime(List<List<Integer>> triangle, int x, int y) {
        //下标不合法
        if (y >= triangleY || x >= triangle.get(y).size()) {
            //下标不合法了就判断是否要跟新min
            minTriangle = Math.min(minTriangle, pathValue);
            return;
        }
        pathValue += triangle.get(y).get(x);
        //遍历右边
        minimumTotalRecursionOverTime(triangle, x, y + 1);
        //遍历左边
        minimumTotalRecursionOverTime(triangle, x + 1, y + 1);
        //左右节点都没了，那么就把这个数给减去
        pathValue -= triangle.get(y).get(x);
    }

    /**
     * 路劲选择
     * 在mxn的格子中，从左上角到右下角一共有多少种走法 只能向下和向右
     * 动态规划
     * dp[i][j] 表示走到这里能有多少种走法  dp[i][j] = dp[i-1][j]+dp[i][j-1]
     * 坐标要合法
     * 初始化多初始化一行防止越界
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    /**
     * 爬楼梯
     * 递归超时
     * 动态规划
     * dp[i]表示在这个位置的跳楼梯方法
     * dp[i] = dp[i-1]+dp[i-2]
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public int climbStairsOverTime(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2) + 1;
    }


    /**
     * 最小时间差
     * 优先小时 绝对值最小   当天     第一天和第二天
     * 24 1     min.(abs.(24-1),abs.(24-1-14))
     * 24 23
     * 按照时间排个序 再挨个找最小时间差
     */
    public int findMinDifference(List<String> timePoints) {
        Collections.sort(timePoints);
        //遍历找到最小的时间差 依次遍历找到最小的 "23:59"
        int min = 20000;
        for (int i = 0; i < timePoints.size() - 1; i++) {
            int n1 = getMinute(timePoints.get(i));
            int n2 = getMinute(timePoints.get(i + 1));
            //全换算成分钟
            min = Math.min(min, n1 - n2);
        }

        int n1 = getMinute(timePoints.get(0));
        int n2 = getMinute(timePoints.get(timePoints.size() - 1));
        int min1 = Math.abs(n2 - n1 - 1440);
        return Math.min(min1, min);
    }

    public int getMinute(String s) {
        int ret = Integer.parseInt("" + s.charAt(0) + s.charAt(1)) * 60 + Integer.parseInt("" + s.charAt(3) + s.charAt(4));
        return ret;
    }

    /**
     * 寻找频繁数
     * 一个数组中有n+1个数，其中这些数字都在1-n之间，求找到这个频繁数
     * 只有一个数字 将他视为一个链表
     * 快慢指针 会有一个环 找到这个环的入口 将nums[i]代表下一个下标
     * 当s和f指针相遇的时候，这时将慢指针从0开始走，和快指针一样每次走一步，相遇时就是入口
     */
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast) {
                return slow;
            }
        }
        return slow;
    }

    /**
     * 跳跃游戏II
     * nums[i] 表示可以跳跃的最大距离 用最少得步数跳到n-1这个位置
     * i 从0位置开始遍历j，遍历的是nums[i]的大小的距离，每次选的是i这个位置加上nums[i]的最大值
     * 使i = j
     */
    public int jump(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for (int i = 0; i < n - 1; ) {
            int prev = i;
            int max = -1;
            int next = -1;
            for (int j = 1; j <= nums[i]; j++) {
                if (prev + j >= n - 1) {
                    return ret + 1;
                }
                if (j + nums[prev + j] > max) {
                    max = j + nums[prev + j];
                    next = j + prev;
                }
            }
            i = next;
            ret++;
        }
        return ret;
    }

    //relax
    public void mainJupm(String[] args) {
        System.out.println(jump(new int[]{2, 3, 1, 1, 4}));
        String t = "111";
        System.out.println(t);
//        System.out.println(Integer.valueOf(t.toString()));
        System.out.println(Integer.parseInt(t));
    }

    /**
     * 组合总和 III
     * 回溯 每次递归选择一个数，当他等于n时，那么就是合适的 k个数的组合
     * 循环遍历这是链表没有选择的数字，每次递归都要使用一个新的链表
     */


    List<List<Integer>> retSum3 = new ArrayList<>();

    //为了防止又相同的元素的组合产生，那么就可以在获取元素的时候给他屏蔽掉，也就是设定start这个起始值，
    //在他之前的都获取不了，这就不会又多种组合产生了
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> ret = new ArrayList<>();
        ret.add(0);
        dfs(1, k, n, ret);

        return retSum3;
    }

    private void dfs(int start, int k, int n, List<Integer> list) {
        if (-list.get(0) == n && k == 0) {
            List<Integer> list1 = new ArrayList<>(list);
            list1.remove(0);
            retSum3.add(list1);
        }
        if (k == 0 || -list.get(0) > n) {
            return;
        }

        for (int i = start; i <= 9; i++) {
            list.set(0, list.get(0) - i);
            list.add(i);

            dfs(i + 1, k - 1, n, list);

            list.set(0, list.get(list.size() - 1) + list.get(0));
            list.remove(list.size() - 1);
        }
    }


    public void mainPassCom(String[] args) {
        combinationSum3(3, 9);
        System.out.println("s");
    }


    public List<List<Integer>> combinationSum3TimeOver(int k, int n) {
        for (int i = 1; i <= 9; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(-i);
            list.add(i);
            comRun(list, k, n);
        }
        //判断重复
        return removeCom(retSum3);
    }

    //判断其中的元素是否相同
    List<List<Integer>> removeCom(List<List<Integer>> r) {
        //可以排序的
        //链表排序
        for (int i = 0; i < r.size(); i++) {
            sortList(r.get(i));
        }
        return remove(r);
    }

    private void sortList(List<Integer> list) {
        //214 124 421 412
        //0 1  1 4 2  142
        for (int i = 0; i < list.size(); i++) {
            int index = i; //421 214
            for (int j = i; j < list.size(); j++) {
                //每次确定一个
                if (list.get(j) < list.get(index)) {
                    swapList(list, index, j);
                }
            }
        }
    }

    //定义链表的第一个数是这个链表数的总和，这个数为负数防止判断数的使用错误
    private void comRun(List<Integer> list, int k, int n) {
        System.out.print(-list.get(0) + " ");
        if (-list.get(0) == n && list.size() == k + 1) {
            list.remove(0);
            retSum3.add(list);
            return;
        }

        if (list.size() == k + 1) {
            return;
        }
        //遍历没有选择的数
        for (int i = 1; i < 9; i++) {
            if (list.contains(i)) {
                continue;
            } else {
                List<Integer> list1 = new ArrayList<>(list);
                list1.add(i);
                list1.set(0, list.get(0) - i);
                comRun(list1, k, n);
            }
        }
    }

    public void mainERR(String[] args) {
        List<List<Integer>> lists = combinationSum3TimeOver(8, 36);
        System.out.println();
    }


    /**
     * 数组中的第K个最大元素
     * 建立一个小根堆，堆的容量就是K，那么这时堆顶的就是第k大的
     */

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(new big());
        int s = 0;
        for (int i : nums) {
            pq.add(i);
            if (pq.size() == k + 1) {
                pq.poll();//这时最小的
            }
        }
        return pq.peek();
    }

    public void mainPassLar(String[] args) {
        findKthLargest(new int[]{1, 2, 3, 4}, 2);
    }

    /**
     * 颜色分类 0 1 2
     * 计数 双指针
     */
    public void sortColors(int[] nums) {
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;

        for (int i : nums) {
            if (i == 0) {
                num0++;
            } else if (i == 1) {
                num1++;
            } else {
                num2++;
            }
        }

        for (int i = 0; i < num0; i++) {
            nums[i] = 0;
        }
        for (int i = num0; i < num1 + num0; i++) {
            nums[i] = 1;
        }
        for (int i = num1 + num0; i < nums.length; i++) {
            nums[i] = 2;
        }
    }

    /**
     * 括号生成
     * 每次移动一个括号，当括号最边上的不能变
     * 要移动俩次 一次右括号，一次左括号err
     * 递归
     */
    List<String> list = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        vector("", n, n);
        return list;
    }

    //左括号的剩余数目要小于右括号，若俩都为零那么给他插入到list中
    //(  )(递归选择
    private void vector(String s, int left, int right) {
        if (left == 0 && right == 0) {
            list.add(s);
            return;
        }
        if (left < right) {//这时插入左右括号都可以
            if (left == 0) {//没有了就只能插入右括号了
                vector(s + ")", left, right - 1);
                return;
            }
            vector(s + "(", left - 1, right);
            vector(s + ")", left, right - 1);
        } else {//相同插入右括号
            vector(s + "(", left - 1, right);
        }
    }

    public void mainPasss(String[] args) {
        List<String> strings = generateParenthesis(3);
        System.out.println("s");
    }

    public List<String> generateParenthesisErr(int n) {
        Set<String> set = new HashSet<>();
        List<String> ret = new LinkedList<>();
        List<String> list = new LinkedList<>();
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            list.add("(");
            str.append("(");
        }
        for (int i = 0; i < n; i++) {
            list.add(")");
            str.append(")");
        }
        set.add(str.toString());
        ret.add(str.toString());
        //每次都移动一个
        int left = n - 1;
        int leftEnd = 1;
        List<String> list1 = new LinkedList<>(list);
//        while (left != 0) {
//            //一次循环完成一个括号的遍历
//            for (int i = left; i+1 < list.size() - leftEnd; i++) {
//                swapList(list, i, i+1);
//                String s = getSByList(list);
//
//                if(!set.contains(s)) {
//                    set.add(s);
//                    ret.add(s);
//                }
//            }
//            left--;leftEnd+=2;
//        }

        int right = n;
        int rightEnd = 0;
        while (right != list.size() - 1) {
            //一次循环完成一个括号的遍历
            for (int i = right; i - 1 > rightEnd; i--) {
                swapList(list1, i - 1, i);
                String s = getSByList(list1);

                if (!set.contains(s)) {
                    set.add(s);
                    ret.add(s);
                }
            }
            right++;
            rightEnd += 2;
        }
        return ret;
    }


    //获得字符串
    String getSByList(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }


    //交换链表
    <T> void swapList(List<T> list, int i, int j) {
        T temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    public void mainWr(String[] args) {
        generateParenthesis(3);

        Set<String> set = new HashSet<>();
        System.out.println("((()))".hashCode());
        System.out.println("(()())".hashCode());
        set.add(")(");
        System.out.println(!set.contains("()"));
        set.add("((()))");
        if (!set.contains("(()())")) {
            set.add("(()())");
            System.out.println("不存在");
        } else {
            System.out.println("存在");
        }
    }

    /**
     * 全排列II
     * 有相同元素 先把仙童元素的所有找完，然后给他去重就好
     * 在每次获取一个元素之后都要删去这个元素，那么就需要用链表来记录元素
     */
    List<List<Integer>> reTII = new ArrayList<>();
    int numLen = 0;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> numsList = new ArrayList<>();
        numLen = nums.length;
        for (int i : nums) {
            numsList.add(i);
        }

        //这里开始递归
        for (int i = 0; i < numsList.size(); i++) {
            List<Integer> copy = new ArrayList<>(numsList);
            copy.remove(i);

            List<Integer> list = new ArrayList<>();
            list.add(numsList.get(i));
            recursion(list, copy);
        }

        reTII = remove(reTII);
        return reTII;
    }

    public void recursion(List<Integer> list, List<Integer> copy) {
        if (list.size() == numLen) {
            reTII.add(list);
            return;
        }

        for (int i = 0; i < copy.size(); i++) {
            //每次取一个数都要删除这个数然后递归 但是原本的不能动
            List<Integer> copy1 = new ArrayList<>(copy);
            copy1.remove(i);

            //创建一个新链表也是这样
            List<Integer> list1 = new ArrayList<>(list);
            list1.add(copy.get(i));

            recursion(list1, copy1);
        }

    }

    /**
     * 判断聊表中的元素是否相等，将他们组装为一个字符串，那么比较这个字符串就好
     */
    List<List<Integer>> remove(List<List<Integer>> r) {
        List<List<Integer>> ret = new ArrayList<>();
        //链表的元素，对应的下标 去重
        HashSet<String> set = new HashSet<>();

        for (int i = 0; i < r.size(); i++) {
            List<Integer> list = r.get(i);

            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < list.size(); j++) {
                sb.append(list.get(j));
            }

            if (!set.contains(sb.toString())) {
                ret.add(list);
                set.add(sb.toString());
            }
        }
        return ret;
    }

    public void mainPassBDwon(String[] args) {
        List<List<Integer>> r = permuteUnique(new int[]{1});
        List<List<Integer>> lists = permuteUnique(new int[]{1});
        System.out.println("s");
    }

    /**
     * 全排列
     * 递归 深度为nums的长度  横向循环的是nums的元素
     * 每次递归会确定一个数，把他加入一个链表中，最终把这个链表放回就好
     * 要知道上一次递归选择的元素来知道这次哪些元素不循环
     */

    List<List<Integer>> reT = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {

        for (int i : nums) {
            List<Integer> list = new ArrayList<>();
            list.add(i);
            recursion(list, nums);
        }
        return reT;
    }

    //递归主体
    public void recursion(List<Integer> list, int[] nums) {
        if (list.size() == nums.length) {
            reT.add(list);
            return;
        }
        for (int i : nums) {
            if (list.contains(i)) {
                continue;
            } else {
                List<Integer> list1 = new ArrayList<>(list);
                list1.add(i);
                recursion(list1, nums);
            }
        }
    }

    public void mainPassxx(String[] args) {
        permute(new int[]{1, 2, 3});
        System.out.println("stop");
        try {

        } finally {

        }
    }


    public void mainn(String[] args) {
        char a = 'g';
        System.out.println(Character.toString(a));
    }

    /**
     * 组合给俩个数n k 放回在1-n的数中k个数组成的所有组合 之前的能用
     * 1 2 3 4     2
     * 1 2
     * 回溯收缩法
     * k表示的是递归层数，n是每次递归的循环，每次递归都能确定一个数，
     * 最终把这些数合起来加入链表中，就是符合要求的子集
     */

    public List<List<Integer>> combinePassDown(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        res.add(new ArrayList<>());

        for (int i = 1; i <= n; i++) {// 遍历所有元素
            // 遍历res的所有子集
            int length = res.size();
            for (int j = 0; j < length; j++) {
                List<Integer> cur = new ArrayList<>(res.get(j));// 这时cur就是子集
                if (cur.size() >= k) {
                    continue;
                }
                // 在最后加上这时这个元素就好
                cur.add(i);
                res.add(cur);

                if (cur.size() == k) {
                    ret.add(cur);
                }
            }
        }

        return ret;
    }

    /**
     * 子集
     * 返回所有可能得子集，不相同的
     * 去重，循环一次删一个
     * 1 2 3
     * 0
     * 1    1
     * 2 12     2
     * 3 13 23 123  3
     * 动态规划
     * dp[i]标识在第i这个元素这里拥有的所有子集，那么在第i+1的子集数目就是i+1这个元素在加上前面的所有情况
     */

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        HashSet<Integer> set = new HashSet<>();

        for (int i : nums) {//遍历所有元素
            if (!set.contains(i)) {
                set.add(i);
                //遍历res的所有子集
                int length = res.size();
                for (int j = 0; j < length; j++) {
                    List<Integer> cur = new ArrayList<>(res.get(j));//这时cur就是子集
                    //在最后加上这时这个元素就好
                    cur.add(i);
                    res.add(cur);
                }
            }
        }
        return res;
    }

    public void mainpa(String[] args) {

        List<List<Integer>> t = subsets(new int[]{1, 2, 2, 3});

        System.out.println("stop");
    }
    //day30

    //day29
    //排序子序列 是连续的一段 包括相同的
    //给定一个数组，看这个数组最少能分成几个子序列
    public void mainNOO(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int count = 0;
        int prevV = in.nextInt();
        int curV = 0;
        boolean state = false;
        for (int i = 1; i < n; i++) {
            curV = in.nextInt();

        }

    }
    //day28

    //二叉树中的最大路径和
    //每走读到一个节点就走到这个节点的左右俩个节点的最大路径
    int MaxPathSum = Integer.MIN_VALUE;

    public int maxPathSumPass(TreeNode root) {
        // write code here
        getMaxPathSum(root);
        return MaxPathSum;
    }

    //要重最后一个节点开始找
    //    1
    //  2   3
    //-1
    private int getMaxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //当前节点的值
        int mv = root.val;

        //不为空就再这个节点再找左右的最大的节点
        int left = getMaxPathSum(root.left);
        int right = getMaxPathSum(root.right);

        //比较大小 左边加中间 右边加中间 左边加右边加中间 中间 自己
        int lm = left + mv;
        int rm = right + mv;
        int all = right + left + mv;
        MaxPathSum = Math.max(Math.max(Math.max(Math.max(lm, rm), all), mv), MaxPathSum);

        //返回也是最大的单条边
        return Math.max(Math.max(left + mv, right + mv), mv);
    }


    //体操队形
    //diff
    //有n个人 输入一个arr数组 arr[i]表示的是i这个人要排到arr[i]前面去
    //也就是再排时 i 的位置时 arr[i] 若arr[i] = i，那么他就是可以随便排
    //1 1 2
    //a b c
    //b a c
    //b c a

    public void mainDIFF(String[] args) {

    }

    //游游的重置数组
    //对输入的一个数进行排列，将他变成偶数 不能有前导零
    // 不行就返回-1 行的话就返回这个数
    public void mainOKArr(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];//最终打印
        int pos = 0;
        for (int i = 0; i < n; i++) {
            int val = in.nextInt();

            //获取val的每一个数
            Stack<Integer> set = new Stack<>();

            //获取每位数 可能有多个0 那么就要吧这个数变为字符串来处理
            String vs = val + "";
            char[] chars = vs.toCharArray();

            //排序
            StringBuilder s = new StringBuilder();
            boolean flag = false;//记录是否含有偶数
            for (int j = 0; j < chars.length; j++) {
                int v = chars[j] - '0';
                if (v % 2 != 0) {
                    s.append(v);
                } else {
                    flag = true;
                }
            }
            if (!flag) {
                arr[pos++] = -1;
                continue;
            }
            for (int j = 0; j < chars.length; j++) {
                int v = chars[j] - '0';
                if (v % 2 == 0) {
                    s.append(v);
                }
            }
            arr[pos++] = Integer.parseInt(s.toString());
        }
        for (int i : arr) {
            System.out.println(i);
        }
    }
    //day27
    //主持人调度2

    //强训标签
    //走迷宫
    //每次可以上下向下走若能从 (s , s)走到(e,e)那么就返回最少步数
    //若不能放回-1
    //.代表能走 *表示不能走
    public void maintry(String[] args) {
        System.out.println((char) 112);

        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()) {//crtl + d 退出
//            int n = scanner.nextInt();
//            System.out.println(n);
//        }
        String s = scanner.nextLine();
        String ss = scanner.next();
        System.out.print(" s = " + s);
        System.out.println("ss = " + ss);
    }

    /**
     * kotori和气球 排列组合
     * 有n种气球，把他们摆成一列m个，俩个颜色相同的不能放一起
     * 若有 4 种，排为4个一列
     * 能排的次数为    4 * (4-1) * (4-1) * (4-1) * (4-1)因为不能和前面相同所以少一种
     */

    public void mainKoto(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        long ret = 0;

        for (int i = 0; i < m; i++) {
            if (ret == 0) {
                ret += n;
                n--;
            } else {
                ret *= n;
                ret %= 109;
            }
        }
        System.out.println(ret);
    }

    //day26 ok

    /**
     * 空调遥控
     * k是室内的温度，n是队员数量，p是进入状态的条件
     * 当 |arr[i]-k|<=p时进入状态
     * 滑动窗口  |arr[i]-k|<=p --> -p <= arr[i]-k <= p
     * 给给定的数组排序，可以知道  对于一个符合要求的区间，左边最小是  arr[l] >= k-p  arr[r] <= k+p
     * 那么就有 arr[r] - arr[l] <= 2p  (k-p，k+p)
     * 那么可以使用l r来维护一个窗口，使得arr[l] - arr[j] <= 2p ，这是这个区间中的数都是有效的，并记录下这时的数
     * 2. 可以先将数组给排序，遍历整个温度的区间，找到这个最小的温度的下标和最大到的小标 这个最小的就是arr[i] - k >= -p 最大的 arr[i] -k <= p
     * 然后他们区间的就都能符合要求，在找这个下标的时候使用二分查找来减少时间
     */

    public void mainTMP(String[] args) {
        Random r = new Random();
        int times = 0;
        while (true) {
            Scanner in = new Scanner(System.in);
            int n = r.nextInt(10, 102004);
            int p = r.nextInt(15, 1024);
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = r.nextInt(1, 100);
            }
//            System.out.println(Arrays.toString(arr));
//            System.out.print("正确:");
            int right = mainPassWindow1(arr, p);
//            System.out.print("测试:");
//            int text = mainText(arr, p);

//            System.out.println("第" + times + "测试" + "结果 = " +( right == text));
//            if (right != text) {
//                System.out.println("错误");
//                return;
//            }
            if (times++ > 10000) {
                break;
            }
        }
    }

    //    public    int mainText(int[] arr, int p) {
    public void mainr(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        } //3  20 39 24 76 63 85 99 37 42 26
//                // 39
        Arrays.sort(arr);

//                int n = arr.length;//9
        int ret = -1;
        for (int i = arr[0]; i < arr[n - 1]; i++) {
            //i 是设置的温度
            int l = i - p;
            int r = i + p;
            //因为二分查找找出来的数是和这个温度下的最近的需求，但是不一定是合法的值，所以需要自己在判断这个点附近的值是否是合法的
            //只是使用二分来减少查找的时间，但不是通过二分直接的到最合适的值，还需要自己来判断
            r = binaryFind(arr, i + p);
            //这俩层循环是为了在这个坐标的左右再来判断是否是合适温度需求
            while (r + 1 < n && arr[r + 1] <= i + p) {//这个坐标下的要比最小的大
                r++;
            }
            while (arr[r] > i + p) {//比最小的小
                r--;
            }
            l = binaryFind(arr, i - p);
            while (l - 1 >= 0 && arr[l - 1] >= i - p) {
                l--;
            }
            while (arr[l] < i - p) {
                l++;
            }
            ret = Math.max(r - l + 1, ret);
        }
        System.out.println(ret);
//            return ret;
    }

    //给定一个指定的值，返回这个值对应的下标或者是最 接近的下标
    // 1  2  4  4  5  7  9   6
    // l        m        r
    public int binaryFind(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }


    public int mainPassWindow1(int[] arr, int p) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int p = in.nextInt();
//        int[] arr = new int[n];
//        for (int i = 0; i < n; i++) {
//            arr[i] = in.nextInt();
//        }
        Arrays.sort(arr);
        int n = arr.length;

        int l = 0, r = 0, ret = -1;
        for (; r < n && l < n; ) {
            if (arr[r] - arr[l] <= 2 * p) {
                ret = Math.max(r - l + 1, ret);
                r++;
            } else {
                l++;
            }
        }
//        System.out.println(ret);
        return ret;
    }

    public void mainNo(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        //<需求，相同的人数>
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int val = in.nextInt();
            map.put(val, map.getOrDefault(val, 0) + 1);
        }
        int k = 0;//设置的温度的高低
        int max = 0;
        Set<Integer> set = map.keySet();
        Integer[] arr = map.values().toArray(new Integer[0]);
        //6 2
        //1 5 3 2 4 6
        //1 2 3 4 5 6
        for (int i : set) {
            int sum = 0;
            for (int j : set) {
                if (Math.abs(j - k) <= p) {
                    sum += map.get(j);
                }
            }
            if (sum > max) {
                k = i;
                max = sum;
            }
        }
        System.out.println(max);
    }

    //不相邻取数
    //动态规划 dp[i]表示再这个位置的最大的数
    //2 6 4 1 100 选了第i-2个就表示不能选i-1个
    //2 6 6 7 106
    //dp[i] = max(dp[i-2]+dp[i],dp[i-1])// 第2个表示没有选那个位值的值 应为即使加上了结果还不入前面那个不加的
    public void mainOKNum(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int[] dp = new int[n + 2];//防止n-2时越界
        int pos = 2;
        for (int i = 0; i < n; i++) {
            int val = in.nextInt();
            dp[pos] = Math.max(val + dp[pos - 2], dp[pos - 1]);
            pos++;
        }
        System.out.println(dp[pos - 1]);
    }

    public void mainTRY1(String[] args) {
        System.out.println(321 % 10);
    }

    /**
     * 小红的ABC
     * 获取一个最短的字符串的长度超过1的回文子串
     * qwq  qwwq qqwawqq 额可以看出三个回文串其实是包含了长度位3的回文串，而第二个包含了长度位2的回文串，
     * 那么就可以知道不管四多大的回文串，都会包含一个长度为2或者位3的回文串，那么只需要枚举所有长度位2或者位3的字符串看是否为回文串就好
     */

    public void mainLittleRed(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        char[] chars = str.toCharArray();

        int n = str.length();
        int ret = -1;
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && chars[i] == chars[i + 1]) {
                ret = 2;
            }
            if (i + 2 < n && chars[i] == chars[i + 2]) {
                ret = 3;
            }
        }
        System.out.println(ret);
    }

    public void mainOverTimeL(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] arr = s.toCharArray();
        int n = arr.length;
        int min = 200;
        int l = 0;
        int r = n - 1;
        while (r > l) {
            while (r > l) {
                if (l + 1 < n && arr[l] == arr[l + 1]) {//2就是最小的
                    System.out.println(2);
                    return;
                }
                //就开始找回文字符串
                if (arr[l] == arr[r]) {
                    //从l r这里开始找
                    int tmpR = r;
                    int tmpL = l;
                    int length = 0;
                    while (tmpR > tmpL) {
                        if (arr[tmpL] == arr[tmpR]) {
                            tmpR--;
                            tmpL++;
                            length += 2;
                        } else {//不同那么直接退出并吧L赋给l
                            l = tmpL;
                            break;
                        }
                    }
                    if (tmpR < tmpL) {//这时说明时个回文字符串
                        min = Math.min(min, length);//比较长度
                        if (min == 2) {
                            System.out.println(2);
                            return;
                        }
                    }
                } else {
                    l++;
                }
            }
            //表示再r这个位置没有回文子串 那么往前走一步
            r--;
        }
        System.out.println(min == 200 ? -1 : min);
    }

    //day25 ok

    /**
     * 分割等和子集 01背包
     * 取出任意个数组看取出的数字的和能否和剩下的相等
     * 凑数 凑sum/2
     * 给一堆数，让你在体积为sum/2的体积下凑出最大的和 如果最终的和和sum/2相同
     * 返回true，否者false
     * 那么有arr[i][j] i指向的是这个数字，j是这个体积 对应的arr[i][j]表示的就是j这个体积下最大的数值
     * arr[i][j] =  max(cur + arr[i-1][j-cur],arr[i-1][j])选了当前的这个数，那么就在剩余的体积下载选一个最大的
     * 没有选这个数，那么就在这个体积下选出一个最大的数
     */
    public void mainChildPass(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int sum = 0;
        int[] vals = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int val = in.nextInt();
            vals[i] = val;
            sum += val;
        }
        if (sum % 2 == 1) {
            System.out.println(false);
            return;
        }
        int v = sum / 2;
        int[][] dp = new int[n + 1][v + 1];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= v; j++) {
                int val = vals[i];
                if (val <= j) {//体积足够放入这个数
                    dp[i][j] = Math.max(val + dp[i - 1][j - val], dp[i - 1][j]);
                } else {//不选这个数，那么就在i-1 j这个体积下找出一个最大的
                    dp[i][j] = dp[i - 1][j];
                }
            }
            if (dp[i][v] == v) {
                System.out.println("true");
                return;
            }
        }
        System.out.println("false");

    }

    public void mainFemLOW(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
//        List<Integer> list = new LinkedList<>();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int val = in.nextInt();
            sum += val;
            arr[i] = val;
//            list.add(val);
        }
        if (sum % 2 == 1) {
            System.out.println(false);
        }
        int count = sum / 2;//要计算的数
        Arrays.sort(arr);
        judge(arr, count, 0);
    }

    public void maineee(String[] args) {
        int[] arr = {100, 99, 97};
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            sum += val;
            arr[i] = val;
//            list.add(val);
        }
        System.out.println(sum % 2);
        System.out.println(sum / 2);
        System.out.println(judge(arr, sum / 2, 0));
        int all = 0;
        for (int i : listSum) {
            all += i;
        }
        System.out.println(all);
    }

    //1 5 11 5   - 11 若相加大大于了，那么就在往前找哇 不要break
    //每递归一次就表示要在改层找到加起来和target相同的 若没有就在玩下递归
    List<Integer> listSum = new ArrayList<>();

    private boolean judge(int[] arr, int target, int sum) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (sum + arr[i] == target) {
                return true;
            }
        }
        //说明不能构成和target相同的数 那么就递归
        for (int i = 0; i < n; i++) {
            //表示不能递归
            if (sum + arr[i] > target || arr[i] == 0) {
                continue;
            }
            //递归时i这个位置的元素不能再参与递归 所以要置为0
            int tmp = arr[i];
            arr[i] = 0;

            listSum.add(tmp);

            if (judge(arr, target, sum + tmp)) {
                return true;
            }
            arr[i] = tmp;//恢复

            listSum.remove(listSum.size() - 1);
        }
        return false;
    }

    private boolean judge1(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            sum += arr[i];
            for (int j = i + 1; j < n; j++) {

            }
        }
        return false;
    }

    //主持人调度
    // 1: 左边排序就行
    // 2;
    //一个数组表示在该时间段有活动，而一个主持人在该时间段只能进行一个活动，判断一个主持人是否能举行完所有的活动
    //[[0,10],[10,20],[15,30]]  结束时间要小于等于开始时间
    // 1 10  5 25  40  70 sum = 59  69 bug 因该是应为是n个活动即将举办这个原因 所以没有这个例子
    //计算除所有活动的时间，在几下最小的开始时间和最大的开始时间
    public boolean hostschedulePass(ArrayList<ArrayList<Integer>> schedule) {
        long maxt = 0;
        long mint = 0;
        long sum = 0;//所有的时间段的集合
        for (int i = 0; i < schedule.size(); i++) {
            int start = schedule.get(i).get(0);
            int end = schedule.get(i).get(1);
            sum += end - start;
            mint = Math.min(start, mint);
            maxt = Math.min(start, maxt);
        }
        System.out.println(maxt - mint);
        if (maxt - mint >= sum) {
            return true;
        }
        return false;
    }


    /**
     * 笨小猴
     * 记录下一个单词中出现次数最多和最少的字母
     */
    public void mainPassFool(String[] args) {
        Scanner in = new Scanner(System.in);
        Map<Character, Integer> map = new HashMap<>();
        int min = 200;
        int max = 1;

        String s = in.nextLine();
        if (s.length() == 0) {

            System.out.println("No Answer");
            System.out.println(0);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        Integer[] arr = map.values().toArray(new Integer[0]);
        for (int i : arr) {
            if (i < min) {
                min = i;
            }
            if (i > max) {
                max = i;
            }
        }
        // System.out.println(max);
        // System.out.println(min);

        if (isPrime(max - min)) {
            System.out.println("Lucky Word");
            System.out.println(max - min);

        } else {
            System.out.println("No Answer");
            System.out.println(max - min);
        }

    }

    //对于质数的考虑是大于1的数，像 0 1 都不是质数
    boolean isPrime(int val) {
        if (val < 2) {
            return false;
        }
        for (int i = 2; i < val; i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
    }


    //day24

    /**
     * 小葱的01串
     * 给一个01串，初始全为白色，把一段连续的区间染成红色，使的红色1等于白色1 白色0等于红色0 放回可能的方法数
     * 每次染色的区间都要确保 红色01等于01总个数的一半 从0开始往后面找
     * 枚举整个区间 区间的长度正好是整个字符串的一半
     * int i = scanf("%s".str);
     * i = -1
     */

    public void maimPassWindow(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String str = in.next();
        int length = n / 2;

        int count1 = 0, count0 = 0;
        for (int i = 0; i < n; i++) {
            if (str.charAt(i) - '0' == 0) {
                count0++;
            } else {
                count1++;
            }
        }
        if (count0 % 2 == 1 || count1 % 2 == 1) {
            System.out.println(0);
            return;
        }

        int l = 0, r = 0, f1 = 0, f0 = 0, ret = 0, indexR = 0;
        for (; l < n; ) {
            if (r - l < length) {//这个是染红的区域
                if (str.charAt(indexR) == '0') {
                    f0++;
                } else {
                    f1++;
                }
                indexR++;
                r++; //这时一个环
                if (r == n) indexR = 0;
            } else {//r - l == length
                if (f0 == count0 / 2 && f1 == count1 / 2) {
                    ret++;
                }

                if (str.charAt(l) == '0') {
                    f0--;
                } else {
                    f1--;
                }
                l++;
            }
        }
        System.out.println(ret);
    }

    /**
     * 判断这个字母是大写还是小写
     * Arr[s.charAt(i) - 'A'] ++
     * arr[s.charAt(i) - 'a'] ++
     * abcaa
     * 01234
     * a-'a' = 0 b -'a' =  1  c -'a' = 2
     * 1 1 1
     * arr 0 1 2
     * a b c
     * arr[26]
     * Arr[26]
     */
    public void mainRedWOverTIme(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        int count1 = 0;
        int count0 = 0;
        for (int j = 0; j < n; j++) {
            if (str.charAt(j) == '0') {
                count0++;
            } else {
                count1++;
            }
        }
        int lengthF = n / 2;
        double f0 = count0 / 2d;
        double f1 = count1 / 2d;
        int ret = 0;
        for (int i = 0; i < n; i++) {//从0开始找
            int tmp0 = 0;
            int tmp1 = 0;
            int index = i;
            for (int j = 0; j < lengthF; j++) {
                if (index == n) {
                    index = 0;
                }
                if (str.charAt(index++) == '0') {
                    tmp0++;
                } else {
                    tmp1++;
                }
                if (tmp0 == f0 && tmp1 == f1) {
                    ret++;
                }
                if (tmp0 > f0 || tmp1 > f1) {
                    break;
                }
            }
        }
        System.out.println(ret);
    }

    /**
     * 最大子矩阵  二维前缀和
     * 0(x-1,y-1) -2 -7(b,y-1)  0
     * 9  2(x,y) -6  2
     * -4  1 -4  1
     * -1(x-1,b)  8  0 (a,b) -2       1 1    2 2
     * 先枚举出所有的子二维数组，对于一个子数组的确定只需要知道左上角和右下角的下标这样就知道了一个二维数组
     * 但是在计算这个二维数组的和的时候，如果还是把他给一个一个的加起来的话，肯定会超时的，这时就要用到浅醉和
     * 对于arr[i][j]位置的和就等于是从(0，0)这个位置的和，那么对于arr[x][y] -> arr[a][b]这个位置的前缀和就等于
     * arr[a][b] - (arr[y-1][b] 上) - (su[b][x-1] - su[y-1][x-1] 左)
     */
    public void mainMAXPASS(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //读这个数组
        int[][] arr = new int[n + 1][n + 1];
        int[][] su = new int[n + 1][n + 1];//实际的坐标向后移了一位
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int val = in.nextInt();
                arr[i][j] = val; //当前位置的前一个矩阵的和 + 当前位置和他上面那列和
                su[i][j] = su[i][j - 1] + val + su[i - 1][j] - su[i - 1][j - 1];
            }
        }

        // x1 y1起始位置  x2 y2 结束位置 枚举所有的子矩阵
        int max = Integer.MIN_VALUE;
        for (int y1 = 1; y1 <= n; y1++) {
            for (int x1 = 1; x1 <= n; x1++) {
                for (int y2 = y1; y2 <= n; y2++) {
                    for (int x2 = x1; x2 <= n; x2++) { //右下角和-右上角和-左侧和
                        int sum = su[y2][x2] - su[y1 - 1][x2] - (su[y2][x1 - 1] - su[y1 - 1][x1 - 1]);
                        max = Math.max(max, sum);
                    }
                }
            }
        }
        System.out.println(max);
    }

    //判断是不是平衡二叉树
    //树的左右俩侧高度步大于1
    //可以优化的
    public boolean IsBalanced_Solution(TreeNode pRoot) {
        return getSolution(pRoot);
    }

    //递归每个节点 的到左右俩边的高度
    private boolean getSolution(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        int r = getHeight(pRoot.right);
        int l = getHeight(pRoot.left);
        if (Math.abs(r - l) > 1) {
            return false;
        }
        return getSolution(pRoot.right) && getSolution(pRoot.left);
    }

    private int getHeight(TreeNode pRoot) {
        if (pRoot == null) {
            return 0;
        }
        return Math.max(getHeight(pRoot.left), getHeight(pRoot.right)) + 1;
    }
    //day23 Ok

    /**
     * 城市群数量 并查集
     * 给一个二维数组arr[i][j]，ij表示俩个城市，如果和俩个城市相连的话，那么arr[i][j]就为1,
     * 如果a和b相连，b和c相连那么也认为a和c相连并认为这是一个城市群，返回城市群的数量
     * 实现一个并查集就行，大小为200
     */

    public void mainUnion(String[] args) {
        unionFind u = new unionFind(200);
        int[][] a = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (a[i][j] == 1) {
                    u.add(i, j);
                }
            }
        }
        System.out.println(u.getUnion());
    }

    public void maint1(String[] args) {
        unionFind u = new unionFind(200);
        u.add(1, 2);
        u.add(2, 3);
        u.add(2, 4);
        u.add(2, 5);
        u.add(7, 5);
        System.out.println(u.getUnion());
    }

    /**
     * 字符串分类
     * 对于俩个字符串A B，如果A能够通过俩个字符中间的交换能的都B，那么就认为A B是同一个字符串
     * 统计每个字符串所含有的字符数量，然后比较字符是否相同，相同就是同一类，不是就是其他类
     * 使用一个arr来统计每个字符的数量，每次每个字符都创建一个arr数组，并使用一个链表来将这些数组保存
     * 如果这个是同一个类就不用加入到链表中，如果是不同的那么就加入都链表中，每次比较遍历链表，最后返回链表的大小
     * 也可以是用哈希表来记录，这样还可以减少查找的次数，先比较俩字符串的长度，在比较每个字符
     */
    public void mainClassification(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            //默认都是小写
            int[] arr = new int[30];
            for (int j = 0; j < s.length(); j++) {
                arr[s.charAt(j) - 'a']++;
            }

            if (list.isEmpty()) {
                list.add(arr);
                continue;
            }

            boolean fg = false;
            for (int[] integers : list) {
                boolean flg = false;
                int[] a1 = integers;
                for (int k = 0; k < a1.length; k++) {
                    if (arr[k] != a1[k]) {//不同那么就退出
                        flg = true;
                        break;
                    }
                }
                if (!flg) {//说明有个相同的，那么就直接退出
                    fg = true;
                    break;
                }
            }
            if (!fg) {//表示没哟一个相同的
                list.add(arr);
            }
        }
        System.out.println(list.size());
    }

    /**
     * 打怪
     * 第一行输入一个数表示的是测试的次数
     * 第二行 h a H A  表示你和小怪的学血量和攻击力
     * 你先发起进攻，饭小怪的血量小于等于0时死亡
     * 返回在活着的条件下能击杀的小怪的最多数目
     * 1
     * 5 1 2 1
     * 小怪死亡的攻击次数， h - n a <= 0 --> n = h / a if h % a > 0 n++;
     * 自己掉的血量 h - n A
     */
    public void mainP(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int h = in.nextInt();
            int a = in.nextInt();
            int H = in.nextInt();
            int A = in.nextInt();
            if (a >= H) {
                System.out.println(-1);
                continue;
            }
            int times = H / a + (H % a != 0 ? 1 : 0);
            int count = 0;
            int l = (times - 1) * A;//杀死一个怪物掉多少的血
            //这个血量下能打死的怪的数目，如果刚好为0了说明最后一个怪在打死的时候自己血量变为0了
            count = h / l - (h % l == 0 ? 1 : 0);
            System.out.println(count);
        }
    }
    //day22 OK

    /**
     * 装箱问题 01 背包
     * 对于V容量的箱子，有n个物品，每个物品对应以个体积，每个物品只能装一次
     * dp[i][j] 表示的是在j这个体积下，挑选i这个物品是时的最大的体积 且这个最大的体积不会超过 V
     * 那么这个dp[i][j]就表示的是在这个体积下的物品的最大的体积
     * 那么对于dp[i][j] 就有俩种状态
     * 不选 dp[i][j] = dp[i-1][j] 那么久应该是在i-1这个物品对应的体积j下装的最大的物品体积
     * 选 dp[i][j] =  v[i] + dp[i-1][j-v[i]] 表示在选了这个物品，然后再j-v[i]这个体积下来找到最大的
     * 这时dp[i][j] 就是选与不选的最大值
     * j的大小就是V i是物品数量
     */
    public int boxin(int V, ArrayList<Integer> num) {
        int n = num.size();
        int[][] dp = new int[n + 1][V + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                if (j - num.get(i - 1) < 0) {//这时的体积V小于这个物品，那么等于前一个就好
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], num.get(i - 1) + dp[i - 1][j - num.get(i - 1)]);
                }
            }
        }
        return V - dp[n][V];
    }

    /**
     * 数组变换
     * 给一个数组，只通过将这个数组中的数值变为他的2倍看能否时候的所有的值都相同
     * 1 2 3
     * 如果这个数组的数字不能变为他最大的数，那么这这样这个数字在怎么变都不会相同，相当于是以最大的数为基准来对起他数进行变化
     */
    public void mainChange(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int max = -1;
        for (int i = 0; i < n; i++) {
            int val = in.nextInt();
            max = Math.max(max, val);
            arr[i] = val;
        }
        for (int i = 0; i < n; i++) {
            int val = arr[i];
            while (val < max) {
                if (val == max) {
                    break;
                }
                val *= 2;
            }
            if (val > max) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }

    boolean isPrime(long val) {
        for (int i = 2; i < val; i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 添加字符
     * 有AB俩字符串
     * abe  A
     * cabc B
     * 可以在A的开头和结尾添加任意的字符 使得A的长度和B相同，并且使得A和B相同位置相同的字符尽可能多
     * 返回的是张最小的不相等的数
     * 滑动串口 在B中找到和A对应最多的，而对应加的字符肯定是相同的
     */
    public void mainPASS(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        char[] A = a.toCharArray();
        char[] B = b.toCharArray();
        int min = 60;
        for (int i = 0; i < b.length(); i++) {
            int cur = 0;
            if (i + a.length() <= b.length()) {

                for (int j = 0; j < a.length(); j++) {
                    if (A[j] != B[i + j]) {
                        cur++;
                    }
                }
            } else {
                break;
            }
            min = Math.min(min, cur);
        }
        System.out.println(min);
    }


    //

    //21
    //最长回文子序列  不改变字符串顺序 只删除和不删除 的到最长的子串
    //有俩个相同的字符就能构成一个回文串，吧这些相加，若还有字符就加1 中间的字符
    // aabbccd  ->  bb aa cc 2

    /**
     * 动态规划 区间dp
     * dp[i][j]表示是在i，j这一区间中的最长的回文子序列，
     * i > j dp[i][j] = 0
     * i = j dp[i][j] = 1
     * i < j
     * 若 str[i] = str[j]   dp[i][j] = dp[i+1][j-1] + 2 表示的是在 i+1，j-1这个区间中的最长的在加上i,j这两个相同字符
     * 若 str[i] != str[j]  dp[i][j] = max(dp[i,j-1],dp[i+1][j]); 表示在i-1和j-1之间的最长所谓回文字符串
     * 填表顺序从下到上 左到右
     * 因为在填当前的ij时会用到ij下面和左边的点，在加上i < j这个条件就能确保数据的正确性并且不会越界
     */
    public void mainpassDP(String[] args) {
        longestPalindromeSubseqPass("bbbab");
    }

    public int longestPalindromeSubseqPass(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];

        //填表
        for (int i = len - 1; i >= 0; i--) {
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else if (i < j) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                    }
                }//i>j不管
            }
        }
        return dp[0][len - 1];
    }

    public void mainDown(String[] args) {
        Scanner in = new Scanner(System.in);
//        System.out.println("aa".substring(0, 1+1));
//        System.out.println(longestPalindromeSubseq(in.nextLine()));
    }

    //n(n^2)++
    public int longestPalindromeSubseq2(String s) {
        int n = s.length();
        int r = n - 1;
        int max = 0;
        while (r > 0 && r > max) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(r) == s.charAt(l)) {
                    StringBuilder tmpS = new StringBuilder(s.substring(l, r + 1));
                    StringBuilder tmpS1 = new StringBuilder(tmpS);
                    tmpS.reverse();
                    if (tmpS1.compareTo(tmpS) == 0) {
                        max = Math.max(max, tmpS.length());
                    }
                }
            }
            r--;
        }
        return max;
    }

    //集合
    public void mainJihe(String[] args) {
        Scanner in = new Scanner(System.in);
        PriorityQueue<Integer> stack = new PriorityQueue<>((Integer a, Integer b) -> {
            return a - b;
        });
        int a = in.nextInt();
        int b = in.nextInt();
        for (int i = 0; i < a + b; i++) {
            int val = in.nextInt();
            if (!stack.contains(val)) {
                stack.add(val);
            }
        }
        int n = stack.size();
        for (int i = 0; i < n; i++) {
            System.out.print(stack.poll() + " ");
        }
    }

    //爱丽丝的人偶
    //对于身高为x的人偶他俩边的人偶不能一个比x高，一个比x矮 不能使有序的
    //  1 2 3 4     2 1 4 3  奇偶交换
    public void mainAilis(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }
        for (int i = 0; i + 1 < n; i += 2) {
            //交换
            System.out.print(arr[i + 1] + " " + arr[i] + " ");
        }
        if (n % 2 == 1) {
            System.out.println(arr[n - 1]);
        }
    }

    public void maintmp(String[] args) {
        System.out.println(Arrays.stream(A.values()).toArray());
    }

    //20day
    //非对称之美
    //求最长的非回文子串长度 有个特殊情况就是全部都是相同的元素
    public void mainERRLittle(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder s = new StringBuilder(in.nextLine());
        StringBuilder tmp = new StringBuilder(s);
        s.reverse();
        if (s.compareTo(tmp) == 0) {
            System.out.println(s.length() - 1);
        } else {
            //是回文串，判断是不是相同的字符
            char c = s.charAt(0);
            boolean flg = false;
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) != c) {
                    flg = true;
                    break;
                }
            }
            if (!flg) {//全部相同
                System.out.println(0);
            } else {
                System.out.println(s.length() - 1);

            }
        }
    }

    boolean cmp(String s1, String s2) {
        int index2 = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) != s2.charAt(index2++)) {
                return false;
            }
        }
        return true;
    }

    //连续子数组的最大数

    /**
     * 动态规划 线性dp
     * dp[i] 表示的就是在i位置下的最大的书
     * dp[i] = Math.max(dp[i-1],0) + nums[i]
     * 因为是连续的子数组，那么如果i-1的最大数都小于了0，那么就没有必要在加上当前的数了，这是当前的这个数就是在这个位置下最大的
     * 那么其实还需要一个变量来记录下最大的数，因为并不知道最大的那段数会出现在那个位置，在最末尾的不一定是最大的数，他只是表示
     * 在i位置下的最大 而不是全局最大
     * -2,1,-3,4,-1,2,1,-5,4
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len + 1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i <= len; i++) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1];
            max = Math.max(max, dp[i]);
        }
        return max;
    }


    //动态规划 dp[i]表示的是到这个位置的最大的数之和
    // dp[i] = max(vals[i]+vals[i-1],vals[i-1]) max = Math.max(dp[i], max);
    // 3 -4 5  5   dp  3 -1 4  dp[i] = dp[i-1]+vals[i-1]  , dp[i]
    // 4 -3 5  6   dp  4  1  6
    public void mainALittleErr(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] vals = new long[n];
        long[] dp = new long[n + 1];//多初始话一个，防止越界
        for (int i = 0; i < n; i++) {
            vals[i] = in.nextLong();
        }
        long max = 0;//错在max的初始化错了，这样就到时最大的可能是个不存在的数
        for (int i = 1; i <= n; i++) {
            dp[i] = Math.max(vals[i - 1] + dp[i - 1], dp[i]);
            max = Math.max(dp[i], max);
        }
        System.out.println(max);
    }

    //俩个人 对立 攻击力a 血量h    光  攻击力b   血量k
    //每次对小红攻击后，他们会互相攻击，若俩边都死了就没事了
    //若只有一边死了，另一边会发起比他的攻击力*10的一次攻击然后死去
    public void mainOk(String[] args) {
        Scanner in = new Scanner(System.in);
        //对立
        long a = in.nextLong();//攻击力
        long h = in.nextLong();
        //光
        long b = in.nextLong();//攻击力
        long k = in.nextLong();

        long hurts = 0;
        while (h > 0 && k > 0) {
            hurts += a;
            hurts += b;
            //互相攻击
            h -= b;
            k -= a;
        }

        if (h <= 0 && k > 0) {//k自爆
            hurts += 10 * b;
            System.out.println(hurts);
        } else if (k <= 0 && h > 0) {
            hurts += 10 * a;
            System.out.println(hurts);
        } else {
            System.out.println(hurts);
        }

    }

    //19day perfect
    //对称之美
    //输入n个字符串，并依此从这n个字符串中取一个字符，看能否构成一个回文字符串，排好的字符串不能再改变
    public void mainSymmetryOk(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        in.nextLine();
        for (int k = 0; k < t; k++) {
            int n = in.nextInt();
            in.nextLine();
            String[] strings = new String[n];
            for (int i = 0; i < n; i++) {
                strings[i] = in.nextLine();
            }
            //判断能否构成
            //使用set来储存支付串有含有的字符，有第一个和最后一个能相同，那么就可以完中间靠
            //若不能那么就返回No
            //  为奇数 a b a       l-0 r-2 剩中间的那个就不用取判断
            //  为偶数 a b b a     r-1 l-2 直接退出
            // 相同会退出
            int l = 0;
            int r = n - 1;
            boolean isEnd = false;
            while (r > l) {
                HashSet<Character> setL = new HashSet<>();
                for (int i = 0; i < strings[l].length(); i++) {
                    setL.add(strings[l].charAt(i));
                }
                HashSet<Character> setR = new HashSet<>();
                for (int i = 0; i < strings[r].length(); i++) {
                    setR.add(strings[r].charAt(i));
                }
                //r判断这个字符是否再l中存在
                boolean isContain = true;
                for (char c : setR) {
                    if (setL.contains(c)) {
                        r--;
                        l++;
                        isContain = false;
                        break;
                    }
                }
                if (isContain) {
                    System.out.println("No");//走到了这里说明已经遍历完了却发现没有相同的
                    isEnd = true;
                }
                if (isEnd) {
                    break;
                }
            }
            if (!isEnd)
                System.out.println("Yes");
        }
    }

    //能获得的礼物的最大值
    //1 3 1
    //1 5 1
    //4 2 1
    //动态规划 使用dp[][]到这个位置能获得的最大的礼物价值
    //只能向右或者向下走
    public void mainGiftOk(String[] args) {
        int[][] arr = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(maxValue(arr));
    }

    public int maxValue(int[][] grid) {
        int m = grid.length;//y
        int n = grid[0].length;//x
        int[][] dp = new int[m + 1][n + 1];//这样课以避免越界
        //初始化dp 将grid的值赋给dp
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = grid[i - 1][j - 1];
            }
        }
        //遍历dp
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + dp[i][j];//左边和上边的最大值
            }
        }
        return dp[m][n];
    }

    //战斗获得战力
    public void mainFightOK(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//怪兽数量
        long initFight = in.nextLong();
        for (int i = 0; i < n; i++) {//
            long monster = in.nextLong();
            if (initFight >= monster) {
                initFight += monster;
            } else {
                //求这俩个的最大公约数
                initFight += getCommonDiv(initFight, monster);
            }
        }
        System.out.println(initFight);
    }

    //辗转相除法
    //5 20    20 / 12 -> 1..8  ->  12 / 8 == 1...4-> 8 / 4 = 2..0 -> 4
    private long getCommonDiv(long initFight, long monster) {
        while (true) {
            long i = monster % initFight;
            if (i == 0) {
                return initFight;
            }
            monster = initFight;
            initFight = i;
        }
    }


    /**
     * *
     * 18
     * 01背包
     * V是背包体积
     * n是物品数量  vw是物品的体积和重量 放回背包能装的最大的重量
     * 动态规划
     * dp[i][j]  i是第i个物品 j表示的事当前的体积
     * 这时dp[i][j]就表示的是在在前i个物品下挑选 j个体积下能去的获得的最大的物品重量
     * 10,2,[[1,3],[10,4]] v m
     * dp[i][j] = max(dp[i-1][j] 表示没有选这个物品,
     * dp[i-1][j-v[i]] + v[i] 选了这个物品 表示的是在i-1个物品中体积在背包剩余大小V-v[i]这个条件下选择的最大的重量
     * 每次都是要找到在挑选第i个物品时，在v这个限制条件下能挑选的最大的重量
     * 这样就会有一个二维的数组 y储存的是挑选的物品 x表示的是在这个体积下能能选择的最大的重量
     * dp[i-1][j-v[i]] + v[i]那么前一个变量i-1 v体积下就是最大的重量 再加上当前的重量就构成了i位置的最大的重量
     * 多初始化一个 这样就能从1开始遍历
     * 10,2,[[1,3],[9,8]]
     */
    //提体积优化 能吧表示每个物品的i优化了 因为再后面没用
    public int knapsack(int V, int n, int[][] vw) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < n; i++) {
            for (int j = V; j >= 0; j--) {//体积
                dp[j] = Math.max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }


    public int knapsackOk(int V, int n, int[][] vw) {
        //v  w
        int[][] dp = new int[n + 1][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {//从1开始找出咋这个j体积下能或的的最大的重量，通过枚举
                if (j - vw[i - 1][0] < 0) {//没有选
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }
        return dp[n][V];
    }

    //chika和蜜桔
    //有m个蜜桔，选n个蜜桔，，第1行为酸度，2行时甜度
    // 得到甜度最高的，且尽可能酸度低 返回第一个为酸度 第二个为甜度
    public void mainOKK(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        Long[] acid = new Long[m];
        Long[] sweet = new Long[m];
        Integer[] sortArr = new Integer[m];
        for (int i = 0; i < m; i++) {
            sortArr[i] = i;
        }
        //使用数组排序
        for (int i = 0; i < m; i++) {
            acid[i] = in.nextLong();
        }

        for (int i = 0; i < m; i++) {
            sweet[i] = in.nextLong();
        }
        //按照甜度排序
        Arrays.sort(sortArr, (Integer o1, Integer o2) -> {//降序
            int ret = (sweet[o1] > sweet[o2]) ? -1 : 1;
            return ret;
        });

        //枚举的到最甜的且在这之上最不酸的
        long maxSweet = 0;
        long minAcid = Long.MAX_VALUE;
        for (int i = 0; i < sortArr.length; i++) {
            long tmpS = 0;
            long tmpA = 0;
            for (int j = i; j < i + n && j < m; j++) {

                tmpS += sweet[sortArr[j]];
                tmpA += acid[sortArr[j]];
            }
            if (tmpS >= maxSweet) {
                maxSweet = tmpS;
                if (minAcid > tmpA) {
                    minAcid = tmpA;
                }
            } else {
                break;
            }
        }
        System.out.println(minAcid);
        System.out.println(maxSweet);
    }

    //字符压缩
    public void mainZip(String[] args) {
        String s = "aabcccccaaa";
        System.out.println(compressString(s));
    }

    public String compressString(String param) {
        char prev = ' ';
        int n = param.length();
        StringBuilder ret = new StringBuilder();
        int count = 1;
        for (int i = 0; i < n; i++) {
            if (param.charAt(i) != prev) {//第一次出现的就给直接加入
                ret.append(param.charAt(i));
                prev = param.charAt(i);
            } else {
                for (; i < n; i++) {//向后找到看有多少相同的
                    if (param.charAt(i) != prev) {//不相同了就加入他的个数然后退出
                        ret.append(count);
                        ret.append(param.charAt(i));
                        prev = param.charAt(i);
                        count = 1;
                        break;
                    }
                    count++;
                }
            }
        }
        if (count != 1) {
            ret.append(count);
        }
        return ret.toString();
    }
    //day17

    public void mainTry(String[] args) {
        int a = 10;
        System.out.printf("%o", a);//8进制输出
        System.out.printf("%x", a);//16
        // 进制输出
    }

    //比那名居的桃子
    //前缀和
    //前缀和是i位置和i位置之前的所有数之和
    public void mainPrevSum(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        long[] sumh = new long[n];
        sumh[0] = in.nextLong();
        for (int i = 1; i < n; i++) sumh[i] = sumh[i - 1] + in.nextLong();

        long[] sums = new long[n];
        sums[0] = in.nextLong();
        for (int i = 1; i < n; i++) sums[i] = sums[i - 1] + in.nextLong();

        int l = 0;
        int r = 0;
        long mins = sums[m - 1];
        long maxh = sumh[m - 1];
        int day = 0;
        //使用前缀和数组，那么在i位置的和就是 sum[i+m-1]-sum[i-1]
        //3 5 1 7
        //4 6 5 1
        long tmps = 0;
        long tmph = 0;
        for (int i = 1; i < n - m + 1; i++) {

            tmph = sumh[i + m - 1] - sumh[i - 1];
            tmps = sums[i + m - 1] - sums[i - 1];

            if (tmph > maxh) {
                maxh = tmph;
                mins = tmps;
                day = i;
            } else if (tmph == maxh && tmps < mins) {
                maxh = tmph;
                mins = tmps;
                day = i;
            }
        }
        System.out.println(day + 1);
    }

    // 长度固定的滑动窗口
    //4 2  桃子的有效期 桃子持续的时间
    //3 5 1 7
    //4 6 5 1
    public void mainSlid(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

        long[] h = new long[n];
        long[] s = new long[n];

        for (int i = 0; i < n; i++) h[i] = in.nextLong();

        for (int i = 0; i < n; i++) s[i] = in.nextLong();

        int l = 0;
        int r = 1;
        int day = 0;
        long happy = h[0];
        long shame = s[0];
        long maxh = 0;
        long mins = 0;
        for (; r < n; r++) {
            //进窗口
            happy += h[r];
            shame += s[r];
            //出窗口
            while (r - l + 1 > k) {
                happy -= h[l];
                shame -= s[l];
                l++;
            }
            //判断是否跟新
            if (happy > maxh) {
                maxh = happy;
                mins = shame;
                day = l;
            } else if (happy == maxh && shame < mins) {
                maxh = happy;
                mins = shame;
                day = l;
            }
        }
        System.out.println(day + 1);
    }


    //十字爆破
    //使用一个数组记录下该行对应的行值和该列对应的列值 m 行 n 列
    //快写 要记得关闭-
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void mainPassPop(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();//行
        int n = in.nextInt();//列
        int[][] arr = new int[m][n];
        int[] col = new int[m];//行和 -->
        int[] row = new int[n];//列 ^
        //将每行 列之和算出
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = in.nextInt();//按一列输入 预处理应该是每列
                arr[i][j] = val;
                //预处理
                row[j] += val;
                col[i] += val;
            }
        }
        System.out.println("stop");

        for (int i = 0; i < m; i++) {//行
            for (int j = 0; j < n; j++) {//列
                int val = row[j] + col[i] - arr[i][j];
                System.out.print(val + " ");
            }
            System.out.println();
        }

    }

    //01 小乐乐改数字
    public void main01OK(String[] args) {
        Scanner in = new Scanner(System.in);
        int i = in.nextInt();
        String s = i + "";
        StringBuilder ret = new StringBuilder();
        for (int j = 0; j < s.length(); j++) {
            if ((s.charAt(j) - '0') % 2 == 0) {
                ret.append(0);
            } else {
                ret.append(1);
            }
        }
        //删取前置零
        StringBuilder r = new StringBuilder();
        boolean flg = false;//第一次不为零的地方
        for (int j = 0; j < ret.length(); j++) {
            if (flg || ret.charAt(j) != '0') {
                flg = true;
                r.append(ret.charAt(j));
            } else {//走到这里就时为零
            }
        }
        if (r.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(r.toString());
        }
    }

    //day 16
    //神奇数
    //得到一个数后，若他的每位数有一位能组成一个质数，那么就是神奇数 输出这个区间内的神奇数的个数
    public void mainMagicPass(String[] args) {
        Scanner in = new Scanner(System.in);
        int l = in.nextInt();
        int r = in.nextInt();
        int[] arr = new int[r - l + 1];
        int pos = 0;
        for (int i = l; i <= r; i++) {
            arr[pos++] = i;
        }

        int ret = 0;
        for (int i = 0; i < arr.length; i++) {
            int val = arr[i];
            //获得每位数
            List<Integer> list = new LinkedList<>();
            while (val != 0) {
                int a = val % 10;
                list.add(a);
                val /= 10;
            }

            //枚举找到神奇数
            //正反枚举
            for (int j = 0; j < list.size(); j++) {
                boolean out = false;
                int a = list.get(j);
                for (int k = j + 1; k < list.size(); k++) {
                    int b = list.get(k);
                    if (isMagic(a * 10 + b) || isMagic(b * 10 + a)) {
                        ret++;
                        out = true;
                        break;
                    }
                }
                if (out) {
                    break;
                }
            }
        }
        System.out.println(ret);
    }

    //是质素
    private boolean isMagic(int i) {
        if (i % 10 == i) {
            return false;
        }
        for (int j = 2; j < i; j++) {
            if ((i % j) == 0) {//除的尽 那么就不是质素
                return false;
            }
        }
        return true;
    }

    //GC出现的频率 给以个字符串和一个int类型，返回这个int类型尺度下的gc比率最长的子串
    //滑动窗口
    //lr表示窗口大小，若长度小于n就r加加有GC就加加几下并当前最长的字符粗，若有更长的就跟新
    //T C A  GC T G T C TTT ACC T CGC
    //C A CGG A G AAA CC A GG T C A G
    public int gsCount(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'G' || c == 'C') {
                count++;
            }
        }
        return count;
    }

    public void maings(String[] args) {
        System.out.println("CCCAAGTCTTCCAATCGTGCCCCCCAATTGAGTCTCGCTCCCCAGGTGAGATACATCAGAAGC".length());
        System.out.println("TCAGCTGTCTTTACCTCGC".length());
        System.out.println("CACGGAGAAACCAGGTCAG".length());

        System.out.println(gsCount("TCAGCTGTCTTTACCTCGC"));
        System.out.println(gsCount("CACGGAGAAACCAGGTCAG"));

    }

    public void mainGCPass(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = in.nextInt();
        int r = 0;
        int l = 0;
        int count = 0; //这时gc的数量
        String ret = "";
        int max = 0;
        while (r < s.length()) {
            char c = s.charAt(r);
            if (r - l != n) {//这时窗口满了要往下就要l++ 这时r先动
                // 窗口中的元素其实是 l到r-1才是 因为如果是r的话会可能在l++时r重复判断 还有可能r加加后到达了窗口长度但是r并没有判断
                //那么是r-1的话就解决了额
                //窗口没有满
                if (c == 'G' || c == 'C') {
                    count++;
                }
                r++;
            } else {
                //窗口满了判断是否要跟新ret
                if (count > max) {
                    max = count;
                    ret = s.substring(l, r);
                    System.out.println(gsCount(ret));
                    System.out.println(ret.length());
                }
                char c1 = s.charAt(l);
                if (c1 == 'G' || c1 == 'C') {
                    count--;
                }
                l++;
            }
        }
        System.out.println(gsCount(ret));
        System.out.println(gsCount("CACGGAGAAACCAGGTCAG"));
        System.out.println(ret);
        System.out.println("TCAGCTGTCTTTACCTCGC".length());
    }

    public void mainGCLOW(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = in.nextInt();
        char[] ret = new char[n];
        //gcbbgcbbgc  使用一个tmp记录最后一个gc也就是当tmp碰到gc就变为gc，若没有就加上这个字母，tmpMax是gc的数量
        //若gcMax 小于了 tmpMax，那么就吧ret更新
        //当得到gc之后就先后走走n-2个数，完事若又
        char[] curS = new char[n];//主要的还是curS遍历，只不过需要记录下最后的GC的G下标
        //下次就从这里开始遍历
        int length = s.length();
        int max = 0;//为当前gc的数量
        for (int i = 0; i < length; i++) {
            int curM = 0;
            int initI = i;//记录起始的i
            int recentG = initI;

            if (i + 1 < length && s.charAt(i) == 'G' && s.charAt(i + 1) == 'C') {//i这个位为gc
                recentG = initI;
                for (int j = 0; j < n && i < length; j++) {
                    curS[j] = s.charAt(i);
                    if (j + 1 < n && s.charAt(i) == 'G' && s.charAt(i + 1) == 'C') {//i这个位为gcc
                        recentG = i;
                        curM++;
                    }
                    i++;
                }
            }

            if (recentG != initI) {//能进入说明不止只有一个gc这时i就从最后的一个gc开始遍历
                i = recentG - 1;//因为最后还会+1
            }

            if (max < curM) {
                //复制给ret
                for (int j = 0; j < curS.length; j++) {
                    ret[j] = curS[j];
                }
                max = curM;
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.print(ret[i]);
        }
    }

    //字符串替换将%s替换为arg中的
    public String formatString(String str, char[] arg) {
        StringBuilder ret = new StringBuilder();
        int n = str.length();
        int argI = 0;
        for (int i = 0; i < n; i++) {
            if (i + 1 < n && str.charAt(i) == '%' && str.charAt(i + 1) == 's') {
                ret.append(arg[argI++]);
                i++;
            } else {
                ret.append(str.charAt(i));
            }
        }
        while (argI < arg.length) {
            ret.append(arg[argI++]);

        }
        return ret.toString();
    }

    //day 15
    //阔普排序
    //先建图 让后在遍历这个图找到入点为0的点退出这个点并吧对应的边删除，更改边指向的点的入点
    //对于入点的计算使用一个数组cnt记录在end下标 遍历这cnt找到为0的
    //**主要是使用一个数组去直接记录下入点 对应下标对应的值就是入点个数
    public void mainOKkUOPU(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        Read read = new Read();
        int count = read.nextInt();
        int lines = read.nextInt();
        int[] cnt = new int[count + 1];
        Map<Integer, List<Integer>> map = new HashMap<>();//str end

        //建表
        for (int i = 0; i < lines; i++) {
            int str = read.nextInt();
            int end = read.nextInt();
            cnt[end]++;//记录入点
            if (map.get(str) == null) {
                map.put(str, new LinkedList<>());
                map.get(str).add(end);
            } else {
                map.get(str).add(end);
            }
        }

        //阔普排序
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i <= count; i++) {
            if (cnt[i] == 0) {
                queue.add(i);
                cnt[i] = -1;
            }
        }
        int[] ret = new int[count];
        int pos = 0;

        while (!queue.isEmpty()) {
            int val = queue.poll();
            ret[pos++] = val;

            //这时改变cnt的值
            for (int i : map.getOrDefault(val, new LinkedList<>())) {
                cnt[i]--;
                if (cnt[i] == 0) {
                    queue.add(i);
                }
            }
            //再次找到为0的点 再次循环就超时了
//            for (int i = 1; i <= count; i++) {
//                if (cnt[i] == 0) {
//                    queue.add(i);
//                    cnt[i] = -1;
//                }
//            }

        }
        if (pos == count) {
            for (int i = 0; i < count - 1; i++) {
                System.out.print(ret[i] + " ");
            }
            System.out.println(ret[count - 1]);
        } else {
            System.out.println(-1);
        }
    }

    public void mainRubbish(String[] args) {
        Scanner in = new Scanner(System.in);
        int point = in.nextInt();
        int side = in.nextInt();

        //建图
        int[][] arr = new int[side][2];
        for (int i = 0; i < side; i++) {
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
        }
        buildMap(arr);

    }

    private void buildMap(int[][] arr) {
        kuoPuMap map = new kuoPuMap();
        for (int i = 0; i < arr.length; i++) {
            map.add(arr[i][0], arr[i][1]);
        }
        System.out.println("stop");
        Map<Integer, kuoPuMap.kuoPuNode> nodeMap = map.map;
        //遍历map找到入点为0的并删除
        Integer[] strArr = map.map.keySet().toArray(new Integer[0]);
        int count = 0;
        while (!map.Nodes.isEmpty()) {
            for (int i = 0; i < strArr.length; i++) {
                if (map.Nodes.contains(strArr[i]) && map.map.get(strArr[i]).penetration == 0) {
                    map.del(strArr[i]);
                    System.out.print(strArr[i] + " ");
                    count++;
                    break;
                }
            }
        }
        if (!map.map.isEmpty()) {
            Integer[] i = map.map.keySet().toArray(new Integer[0]);
            System.out.println(i[0]);
            count++;
        }

    }

    //shift
    class kuoPuMap {

        class kuoPuNode {
            int node = 0;//节点值
            List<kuoPuNode> sides = new LinkedList<>();//节点指向的节点值
            int penetration = 0;

            kuoPuNode(int str) {
                node = str;
            }

            void addSide(kuoPuNode endNode) {
                endNode.penetration++;//对应节点的入点加加
                sides.add(endNode);
            }
        }

        Set<Integer> Nodes;//开始节点的数量
        Map<Integer, kuoPuNode> map = new HashMap<>();//储存节点

        public kuoPuMap() {
            Nodes = new HashSet<>();
        }

        public void del(int val) {
            kuoPuNode node = map.get(val);//获得node对应的节点
            //删除这个节点，和他指向的终点 修改终点的入点
            for (int i = 0; i < node.sides.size(); i++) {//遍历整个终点数组减少入点数目
                kuoPuNode cur = node.sides.get(i);
                cur.penetration--;
            }
            node.sides.clear();//清空终点数组
            map.remove(val);
            Nodes.remove(val);
        }

        public void add(int str, int end) {
            checkPoint(str, end);
            //获得节点
            kuoPuNode strNode = map.get(str);
            kuoPuNode endNode = map.get(end);
            //加入节点
            strNode.addSide(endNode);
//            strNode.sides.add(end);//起始界定加入终点
//            endNode.penetration++;//终点节点入点++
            //将起始节点加入节点数组
            Nodes.add(str);
        }

        public void checkPoint(int str, int end) {
            if (!map.containsKey(str)) {//不存这这个开始节点 创建新节点
                kuoPuNode node = new kuoPuNode(str);
                map.put(str, node);
            }
            if (!map.containsKey(end)) {
                kuoPuNode node = new kuoPuNode(end);
                map.put(end, node);
            }
        }
    }


    public void mainLOW(String[] args) {
        Scanner in = new Scanner(System.in);
        HashMap<Integer, ListN> map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        int n = in.nextInt();
        int lenSize = in.nextInt();
        for (int i = 0; i < lenSize; i++) {//俩个数表示 a->b
            int str = in.nextInt();
            int end = in.nextInt();

            set.add(str);
            set.add(end);
            if (!map.containsKey(str)) {
                map.put(str, new ListN(str));
            }
            if (!map.containsKey(end)) {
                map.put(end, new ListN(end));
            }

            map.get(str).next = map.get(end);
        }
        for (int i : set) {
            ListN cur = map.get(i);
            int[] ret = new int[n];
            int useSize = 0;
            while (cur != null) {
                ret[useSize++] = cur.val;
                cur = cur.next;
            }
            if (useSize == n) {
                for (int j = 0; j < useSize; j++) {
                    System.out.print(ret[j] + " ");
                }
            }
        }
    }

    //分组
    //每次枚举，不是按人数来分组，而是通过每组的最多人数来分株
    //当这个分组的组数小于等于要分的组的是，这时的就是最小的组数
    //反推
    public void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//总共的人数
        int m = in.nextInt();//要分的组数

        int maxH = 0;
        HashMap<Integer, Integer> map = new HashMap<>();//记录每个声部有多少个人
        for (int i = 0; i < n; i++) {
            int tmp = in.nextInt();
            map.put(tmp, map.getOrDefault(tmp, 0) + 1);
            maxH = Math.max(maxH, map.get(tmp));
        }
        if (map.size() > m) {
            System.out.println(-1);
            return;
        }
        //二分优化这这里
        int left = 1;
        int right = maxH;
        while (left < right) {
            int mid = (left + right) / 2;
            if (check(mid, m, map)) {//若能进入说明分的组人数小了有可能是最小的人数,继续往下分
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(right);
        //从1-max开始枚举
        for (int i = 1; i <= maxH; i++) {//每组最多i人
            int count = 0;
            for (int j : map.values()) {
                count += j / i + j % i == 0 ? 0 : 1;
            }
            if (count <= m) {//因为是从小开始去取得最小人数
                System.out.println(i);
                return;
            }
        }
    }

    //最多x个人，count是分组数量
    boolean check(int x, int m, HashMap<Integer, Integer> map) {
        int count = 0;
        for (int j : map.values()) {
            count += j / x + (j % x == 0 ? 0 : 1);
        }
        return count <= m;
    }

    //平方树，给一个数给到里他最近得平方数 long
    public void mainPow(String[] args) {

        while (true) {
            Scanner in = new Scanner(System.in);
            long n = in.nextLong();
            long min = 0;//记录得时最近得数字
            long val = (long) Math.sqrt(n);
            long len = Long.MAX_VALUE;
            if (len > Math.abs(Math.pow(val, 2) - n)) {
                min = val;
                len = (long) Math.abs(Math.pow(val, 2) - n);
            }
            if (len > Math.abs(Math.pow(val + 1, 2) - n)) {
                min = val + 1;
                len = (long) Math.abs(Math.pow(val + 1, 2) - n);
            }
            if (len > Math.abs(Math.pow(val - 1, 2) - n)) {
                min = val - 1;
                len = (long) Math.abs(Math.pow(val + 1, 2) - n);
            }
            System.out.println((long) Math.pow(min, 2));
        }
    }

    //day 14
    //数组元素得移除，并获得最大得值
    //移除ai 同时等于ai-1 和ai+1 得值都会被移除 这时获得ai分
    //动态规划
    public void mainOK(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //f[i]表示的是选了i这个位置的数 f[i] = g[i-1]+f[i] 不选i-1加上当前这个位置选
        //g[i]表示不选i这个位置得数 g[i] = max(f[i-1],g[i-1]) 因为i-1这个位置可以选可以不选
        int N = 10_000 + 10;
        int[] f = new int[N];
        int[] g = new int[N];
        int[] sum = new int[N];
        for (int i = 0; i < n; i++) {
            int index = in.nextInt();
            sum[index] += index;
        }

        for (int i = 1; i < N; i++) {//不存在0的
            int val = sum[i];
            f[i] = val + g[i - 1];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        System.out.println(Math.max(f[f.length - 1], g[g.length - 1]));
    }

    public void mainLOWArr(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            count += arr[i];
            int tmp = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] == tmp - 1) {
                    i--;
                } else {
                    break;
                }
            }
        }
        System.out.println(count);
    }

    //队伍得平均值
    public void mainAve(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n * 3];
        for (int i = 0; i < n * 3; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        long max = 0;//有错先看看是不是小了
        for (int i = n; i < n * 3; i += 2) {
            max += arr[i];
        }
        System.out.println(max);
        //1 2 3 4 5 6 7 8 9
        // 1 8 9   2 4 5   3 6 7
        //123 454 321 34 5 3 24 33 3 23 43 23
//        3 3 5     23   23 24    33 34 43    123 321 454

    }

    //乒乓球得包含
    public void mainPiPo(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String s1 = in.nextLine();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char tmp = s1.charAt(i);
            if (map.containsKey(tmp)) {
                map.put(tmp, map.get(tmp) + 1);
            } else {
                map.put(tmp, 1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            if (map.containsKey(tmp)) {
                map.put(tmp, map.get(tmp) - 1);
            }
            if (map.containsKey(tmp) && map.get(tmp) == 0) {
                map.remove(tmp);
            }
        }
        if (map.isEmpty()) {
            System.out.println("yes");
        } else {
            System.out.println("No");
        }
    }

    //按身高排序  可以创建一个类储存这俩的联系，比较是就通过这个类，
    // 也可以使用hashmap只不过身高可能会相同，那么就需要使用String[]数组来储存名字map<Integer,String[]>
    // 这里使用按下标排序，额外创建一个数组用来储存下标，比较的还是身高
    // 只不过再交换的时候是交换的是交换的下标
    public void mainHeight(String[] args) {
        String[] s = {"Mary", "John", "Emma"};
        int[] height = {180, 165, 170};
        sortPeople(s, height);
    }

    public String[] sortPeople(String[] names, int[] heights) {
        int n = heights.length;
        Integer[] index = new Integer[n];//index[i]表示的是身高对应的下标
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
//        comIndex c = new comIndex(heights);
        Arrays.sort(index, (Integer i, Integer j) -> {//要传入的是类
            return heights[j] - heights[i];
        });

        /*
        for (int i = 0; i < n; i++) {//不能同过flg优化，因为他这是降序的排序
            for (int j = i; j < n; j++) {
                if (heights[index[i]] < heights[index[j]]) {
                    //交换下标数组
                    int tmp = index[i];
                    index[i] = index[j];
                    index[j] = tmp;
                }
            }
        }
        */
        String[] strings = new String[n];
        for (int i = 0; i < n; i++) {
            strings[i] = names[index[i]];
        }
        return strings;
    }

    //k次取反后的数组最大
    public void mainLar(String[] args) {
        int[] arr = {4, 2, 3};

        largestSumAfterKNegations(arr, 1);
    }

    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        int[] negative = new int[n];//记录每个负数的下标
        int user = 0;
        int min = 0;
        int count = 0;
        boolean flg = true;
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) {
                negative[user++] = i;
            } else {
                if (flg) {
                    min = i;
                    flg = false;
                }
            }
            count += nums[i];
        }
        if (k <= user) {//吧负数全部变为正的
            for (int i = 0; i < k; i++) {
                nums[negative[i]] = -nums[negative[i]];
                count += nums[negative[i]] * 2;
            }
        } else {//k>user
            for (int i = 0; i < user; i++) {
                nums[negative[i]] = -nums[negative[i]];
                count += nums[negative[i]] * 2;

                if (nums[negative[i]] < nums[min]) {
                    min = negative[i];
                }
            }
            k = k - user;
            if (k % 2 == 1) {
                nums[min] = -nums[min];
                count += nums[min] * 2;
            }
        }
//        for (int i : nums) {
//            count += i;
//        }
        return count;
    }
    //day13

    /**
     * 字符串可能的情况
     * 当最多的字符的数量大与与字符粗总长度(n+1)/2是，这个字符串不能重排序
     * 先将数组的奇数为全部放了，然后剩下的随便放都是可以满足条件的
     */

    public void mainEm(String[] args) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 0);
        System.out.println(map.isEmpty());
    }

    public void mainPassNow(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        Integer[] values = map.values().toArray(new Integer[0]);
        Character[] chars = map.keySet().toArray(new Character[0]);
        int size = values.length;

        //对chars排序
        Integer[] sortChars = new Integer[size];
        for (int i = 0; i < size; i++) {
            sortChars[i] = i;
        }
        Arrays.sort(sortChars, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return values[o1] - values[o2];
            }
        });
        //sortChars[size-1]的就是最大的数
        if (values[sortChars[size - 1]] > (n + 1) / 2) {
            System.out.println("No");
            return;
        }

        //chars下标指向的values就是该字母出现的次数
        int end = size - 1;
        int index = sortChars[end];
        char[] chars1 = new char[n];
        for (int i = 0; i < n; i += 2) {
            chars1[i] = chars[index];
            values[index] -= 1;
            if (values[index] == 0) {//这时最多的元素已经添加完了
                end -= 1;
                index = sortChars[end];//往前面添加
            }
        }
        for (int i = 1; i < n; i += 2) {//添加偶数
            if (values[index] != 0) {
                chars1[i] = chars[index];
                values[index] -= 1;
            } else {
                end -= 1;
                i -= 2;//不要完后走
                index = sortChars[end];//往前面添加
            }
        }
        System.out.println(Arrays.toString(chars1));
    }

    private int getMaxV(Integer[] values) {
        int max = 0;
        int index = 0;
        for (int i = 0; i < values.length; i++) {
            if (values[i] > max) {
                index = i;
                max = values[i];
            }
        }
        return index;
    }

    public void mainOverTime(String[] args) {
        Scanner in = new Scanner(System.in);
        myMap map = new myMap();
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        for (int i = 0; i < str.length(); i++) {
            map.put(str.charAt(i));
        }
        System.out.println("sout");
        int[] counts = map.getCount();
        char[] chars = map.getChars();
        int tmpCount = 0;
        char maxChar = ' ';
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != map.MaxCount) {
                tmpCount += counts[i];
            } else {
                maxChar = chars[i];
            }
        }
        if (tmpCount + 1 >= map.MaxCount) {
            System.out.println("yes");
            StringBuilder s = new StringBuilder();
            s.append(maxChar);
            while (true) {
                for (int j = 0; j < chars.length; j++) {
                    if (counts[j] != 0) {
                        s.append(chars[j]);
                        counts[j]--;
                    }
                }
                if (s.length() == n) {
                    break;
                }
            }
            System.out.println(s);
        } else {
            System.out.println("no");
        }
    }

    public void mainLowC(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        char[] isContain = new char[n];
        int userSize = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(str.charAt(i))) {//不存在
                map.put(str.charAt(i), 1);
                isContain[userSize++] = str.charAt(i);
            } else if (map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
                max = Math.max(map.get(str.charAt(i)), max);
            }
        }
        int count = 0;
        char macC = ' ';
        for (int i = 0; i < userSize; i++) {
            if (map.get(isContain[i]) != max) {
                count += map.get(isContain[i]);
            } else {
                macC = isContain[i];
            }
        }
        if (count + 1 >= max) {
            System.out.println("yes");
            StringBuilder ret = new StringBuilder();
            ret.append(macC);
            map.put(macC, map.get(macC) - 1);

            while (true) {
                for (int i = 0; i < userSize; i++) {
                    if (map.get(isContain[i]) != 0) {
                        ret.append(isContain[i]);
                        map.put(isContain[i], map.get(isContain[i]) - 1);
                    }
                }
                if (ret.length() == n) {
                    break;
                }
            }
            System.out.println(ret);
        } else {
            System.out.println("no");
        }
    }

    /**
     * 放回最长不相同的子数组
     * arr[i]就是到i点的最长不连续的子数组
     * 到i的长度就是前一个的长度加上当前这个不相同的长度
     * 使用max记录最长的，使用hashset来记录子串的元素，若有相同的就把这个set清空，
     * 在吧这个相同的加入，并设置该点为1
     * a little是因为没有回滚在遇到相同的数字时
     * 应该使用map去储存值和下标 然后在遇到相同的就回滚到第一个相同的下一个位置
     */
    public void mainOKk(String[] args) {
        int[] a = {2, 2, 3, 4, 3, 55, 33, 22, 43};
        System.out.println(maxLength(a));
    }

    //滑动窗口
    //使用left 和right 当有相同的left 加加 没有就right++
    //使用set记录是否有相同的，有就吧他出出去
    public int maxLength(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int ret = 0;
        HashSet<Integer> set = new HashSet<>();
        while (r < n) {
            if (!set.contains(arr[r])) {
                set.add(arr[r]);
                ret = Math.max(ret, r - l);
                r++;
            } else {//存在
                set.remove(arr[l]);
                l++;
            }
        }
        return ret + 1;//因为下标时从0开始算的，实际的长度要加1
    }

    public int maxLengthLowOK(int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return 0;
        }
        int max = 1;
        Map<Integer, Integer> map = new HashMap<>();//值 下标
        int[] arrLength = new int[n];
        map.put(arr[0], 0);
        arrLength[0] = 1;
        for (int i = 1; i < n; i++) {
            if (!map.containsKey(arr[i])) {//不存在这个
                arrLength[i] = arrLength[i - 1] + 1;
                max = Math.max(arrLength[i], max);
                map.put(arr[i], i);
            } else {//存在

                i = map.get(arr[i]) + 1;//回滚到下一位
                arrLength[i] = 1;
                map.clear();
                map.put(arr[i], i);
            }
        }
        return max;
    }

    /**
     * t 测试次数 n 字符长度 k 连胜奖励的分数
     */
    public void mainLushi(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
//        in.next();
        for (int i = 0; i < t; i++) {
            int n = in.nextInt();//字符的长度
            int[] mark = new int[n];//mark[i]是到这个点或的的分数
            int k = in.nextInt();
            in.nextLine();// 吧空行取了
            String str = in.nextLine();
            if (str.charAt(0) == 'W') {
                mark[0] = 1;
            } else {
                mark[0] = -1;
            }
            for (int j = 1; j < n; j++) {
                if (str.charAt(j) == 'L') {//输了
                    mark[j] = mark[j - 1] - 1;
                } else if (j - 2 >= 0 && str.charAt(j - 2) == 'W' && str.charAt(j - 1) == 'W'
                        && str.charAt(j) == 'W') {
                    mark[j] = mark[j - 1] + k;
                } else {
                    mark[j] = mark[j - 1] + 1;
                }
            }
            System.out.println(mark[n - 1]);
        }
    }

    //力扣
    public void main121(String[] args) {
        mainRun m = new mainRun();
        int[] arr = {-1, 0, 4, 0, 1};
        String s = "abbba";
        int[] ret = m.findSubtreeSizes(arr, s);
        System.out.println("stop");
    }

    //修改后的大小
    public int[] findSubtreeSizes(int[] parent, String s) {
        int n = parent.length;
        for (int x = 1; x < n; x++) {
            int y = getRootI(x, parent, s);//为-1说明就不存在这个y
            if (y != -1) {
                parent[x] = y;
            }
        }
        //计算每个节点的个数
        int[] ret = getCount(parent);
        return ret;
    }

    private int[] getCount(int[] parent) {
        int n = parent.length;
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            //遍历每个下标
            int x = i;
            while (x >= 0) {
                ret[x] += 1;
                x = parent[x];
            }
        }
        return ret;
    }

    private int getRootI(int i, int[] parent, String s) {
        int y = 0;
        int t = i;
        while (i >= 0) {//i = 0 y = -1
            y = parent[i];
            if (y >= 0 && s.charAt(y) == s.charAt(t)) {
                return y;
            }
            i = y;
        }
        return -1;
    }

    /**
     * 输错的字符
     */
    public int possibleStringCount(String word) {
        int ret = 1;
        int n = word.length();
        char prev = ' ';
        for (int i = 0; i < n; i++) {
            if (prev == word.charAt(i)) {
                ret++;
            }
            prev = word.charAt(i);
        }
        return ret;
    }

    public void mainCharErr(String[] args) {
        System.out.println(possibleStringCount("cccc"));
    }
    //day12

    /**
     * mari 很 shiny
     */
    //动态规划 使用s1记录下s出现的次数，然后再用h1记录下sh出现的次数，最后用y1记录下shy出现的次数
    //s1 = ‘s'  h1 += sh  y1 += h1 因为记录的是shy出现的次数，而shy也就是由s+h+y组成的
    //所以只需要先记录下s出现的次数，然后碰到h时加上当前的s，这得到了这时sh的个数，然后再碰到y时又加上sh的个数，这样就的到了shy的个数
    public void mainShy(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String str = in.nextLine();
        char[] arr = str.toCharArray();
        long s = 0, h = 0, y = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 's') {
                s++;
            } else if (arr[i] == 'h') {
                h += s;
            } else if (arr[i] == 'y') {
                y += h;
            }
        }
        System.out.println(y);
    }

    public void mainlow(String[] args) {
//        System.out.println(Long.MAX_VALUE);
        Scanner in = new Scanner(System.in);
        HashMap<Character, Long> map = new HashMap<>();
        map.put('s', 0L);
        map.put('s', 0L);
        map.put('h', 0L);
        map.put('y', 0L);
        in.nextLine();
        String s = in.nextLine();
        long ret = 0L;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 's') {
                map.put('s', map.get('s') + 1);
            } else if (s.charAt(i) == 'h') {
                map.put('h', map.get('h') + 1);
            } else if (s.charAt(i) == 'y') {
                ret += map.get('s') * map.get('h');
                map.put('s', 0L);
                map.put('h', 0L);
            }

        }
        System.out.println(ret);
    }

    /**
     * 找到第一个相同的节点
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>();
        for (ListNode node = pHead1; node != null; node = node.next) {
            set.add(node);
        }
        for (ListNode i = pHead2; i != null; i = i.next) {
            if (set.contains(i)) {
                return i;
            }
        }
        return null;
    }

    /**
     * 删除删除相同的字符
     *
     * @param args
     */
    public void mainDelC(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        Set set = new HashSet();
        for (int i = 0; i < s2.length(); i++) {
            set.add(s2.charAt(i));
        }
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < s1.length(); i++) {
            if (!set.contains(s1.charAt(i))) {
                ret.append(s1.charAt(i));
            }
        }
        System.out.println(ret);

    }
    //day11

    /**
     * 逆置字符串
     *
     * @param args
     */
    public void mainEZ(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] strs = s.split(" ");
        List<String> list = new LinkedList<>();
        for (String si : strs) {
            list.add(si);
        }
        Collections.reverse(list);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    /**
     * 买进股票的最好时机II
     *
     * @param args
     */

    //只要是有加那么就卖
    public void mainSell(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] vals = new int[n];
        for (int i = 0; i < n; i++) {
            vals[i] = in.nextInt();
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (i < n - 1 && vals[i + 1] - vals[i] > 0) {
                ret += vals[i + 1] - vals[i];
            }
        }
        System.out.println(ret);
    }

    public void mainII(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] vals = new int[n];
        for (int i = 0; i < n; i++) {
            vals[i] = in.nextInt();
        }

        //找到最低点买进和最高顶卖出
        int ret = 0;
        int min = vals[0];
        int max = vals[0];
        for (int i = 0; i < n; i++) {
            while (i < n - 1 && vals[i] == vals[i + 1]) {//去除相同的额情况留下最后一位
                i++;
            }
            if (i + 1 < n && vals[i] - vals[i + 1] < 0) {//i为最低
                min = vals[i];
                while (i < n - 1 && vals[i + 1] - vals[i] > 0) {//从这里向后找到最高点
                    i++;
                }
                max = vals[i];
                ret = ret + max - min;
            }
        }
        System.out.println(ret);
    }

    /**
     * you you的礼包 数字很大要用long
     * 需要枚举出所有情况，当当只是取一边的所有和剩下一边的加起来是不对的
     */
    //枚举
    public void mainYY(String[] args) {
        Scanner in = new Scanner(System.in);
//        Integer.MAX_VALUE
        int a, b, apple, peach;
        apple = in.nextInt();//苹果
        peach = in.nextInt();//桃子
        a = in.nextInt();//礼包a 2平 + 1桃
        b = in.nextInt();//礼包b 1平 + 2桃
        long ret = -1;
        //依此枚举出a b礼包的数量让然后计算最大值
        for (long i = 0; i <= Math.min(apple / 2, peach); i++) {//a
            long y = Math.min(apple - i * 2, (peach - i) / 2);//b
            ret = Math.max(ret, i * a + y * b);
        }
        System.out.println(ret);
        // System.out.println("stop");
    }

    //贪心是错的，若a > b就狂选a 这样不行
    static int n, m;//将数量设置为全局的

    public void mainYouLow(String[] args) {
        int a, b;
        Scanner in = new Scanner(System.in);
        n = in.nextInt();//苹果
        m = in.nextInt();//桃子
        a = in.nextInt();//礼包a 2平 + 1桃
        b = in.nextInt();//礼包b 1平 + 2桃
        int ret = 0;
        if (a > b) {//优先a礼包
            ret += getPrice(n, m, a);
            //剩下的看能不能组成b礼包
            ret += getPrice(m, n, b);
        } else {//优先b礼包
            ret += getPrice(m, n, b);
            //剩下的看能不能组成a礼包
            ret += getPrice(n, m, a);
        }
        System.out.println(ret);
    }

    //计算n m的限制下能的到的a礼包最多的情况 a = 2n+1m
    int getPrice(int n, int m, int a) {
        int ret = 0;
        if (m * 2 <= n) {
            ret += m * a;//以m为a限制条件
            mainRun.n -= m * 2;
            mainRun.m = 0;
        } else {
            int tmp = n / 2;//以n为a限制
            ret += tmp * a;
            mainRun.m -= tmp;
            mainRun.n -= tmp * 2;
        }
        return ret;
    }

    //day10

    /**
     * 过河兵 超时
     */

    //动态规划 路径选择
    //dp[y][x] = dp[y-1][x-1]+dp[y][x-1]  dp[y][x】表示的到这个点的路径数
    //初始化时多出一行和一列会少很多麻烦，1 1处为1其他全为0
    public void mainPass(String[] args) {
        Scanner s = new Scanner(System.in);
        //最终稿走到（n,m）
        n = s.nextInt();//x
        m = s.nextInt();//y
        horseX = s.nextInt();
        horseY = s.nextInt();
        long[][] dp = new long[m + 2][n + 2];//n = 2 实际上有3行 数会非常大
        dp[0][1] = 1;
        System.out.println(getRoadCountByDp(dp, horseX + 1, horseY + 1, n + 1, m + 1));
    }

    private long getRoadCountByDp(long[][] dp, int horseX, int horseY, int n, int m) {

        //走到了m n结束d
        for (int i = 1; i <= m; i++) {//y
            for (int j = 1; j <= n; j++) {//x
                if (Math.abs(j - horseX) + Math.abs(i - horseY) == 3 && j != horseX && i != horseY) {//这个地方会被马吃
                    dp[i][j] = 0;
                } else if (j == horseX && i == horseY) {//马这个位置也不能走
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    int[][] horse = new int[9][2];
    HashMap<Integer, Integer> hashHorse;//map<x,y>
    int horseX, horseY;//马所在的位置

    //       int n,m;//x,y最终走到的位置
    public void mainLower(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();//x
        m = s.nextInt();//y
        horseX = s.nextInt();
        horseY = s.nextInt();
        //得出horse能走的坐标 使用公式就能解决
//        int[] x = {2, -2};
//        int[] y = {2, -2};
//        int[] lr = {1, -1};
//        int arrIndex = 0;
//        hashHorse = new HashMap<>();
//        for (int i = 0;i < 2;i++) {//遍历x,y
//            for (int j = 0; j < 2; j++) {//x+|2|
//                horse[arrIndex][0] = horseX + x[i];
//                horse[arrIndex++][1] = horseY + lr[j];
//            }
//            for (int j = 0; j < 2; j++) {//y+|2|
//                horse[arrIndex][0] = horseX + lr[j];
//                horse[arrIndex++][1] = horseY + y[i];
//            }
//        }
//        horse[8][0] = horseX;
//        horse[8][1] = horseY;

        System.out.println("stop");
        System.out.println(getRoadCount(0, 0));
    }

    //每次只能是向右走或者是向下走 目的地点是(n,m)
    int[] soldierX = {1, 0};
    int[] soldierY = {0, 1};

    int getRoadCount(int x, int y) {
        int ret = 0;
        if (x == n && y == m) {
            return 1;
        } else if (x > n || y > m) {
            return ret;
        }
        //向右和向下走
        for (int i = 0; i < 2; i++) {
            int curX = x + soldierX[i];
            int curY = y + soldierY[i];
            if (curX >= 0 && curX <= n && curY >= 0 && curY <= m) {//坐标合法
                //看当前这个位置的是不是被马吃的位置
                boolean flg = false;//能否被马吃
                if ((Math.abs(curX - horseX) + Math.abs(curY - horseY) == 3) && curX != horseX && curY != horseY) {
                    flg = true;
                }
                if (curX == horseX && curY == horseY) {//不能走到马那个位置
                    flg = true;
                }
//                for (int j = 0; j < horse.length; j++) {
//                    if (curX == horse[j][0] && curY == horse[j][1]) {//被吃了
//                        //那么就不能递归这个坐标
//                        flg = true;
//                        break;
//                    }
//                }
                //走到了这里说明不会被马吃 递归
                if (!flg) {
                    ret += getRoadCount(curX, curY);
                }
            }
        }
        return ret;
    }

    /**
     * 买卖股票的最好时机
     *
     * @param args
     */
    public void mainBuy(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] val = new int[n];
        for (int i = 0; i < n; i++) {
            val[i] = in.nextInt();
        }
        int ret = -1;
        int prevMin = Integer.MAX_VALUE;
        for (int i : val) {
            prevMin = Math.min(i, prevMin);
            ret = Math.max(i - prevMin, ret);//假设每次的i都是最大值
        }
        System.out.println(ret);
    }

    /**
     * 最长的回文字符串 O(n^2)
     */
    public void mainBe(String[] args) {
        System.out.println(getLongestPalindromeBE("ababa"));
    }

    public int getLongestPalindromeBE(String A) {
        //从中心点开始向俩边取找回文串
        int n = A.length();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            //为奇数的情况
            int right = i + 1;
            int left = i - 1;
            while (left >= 0 && right < n && A.charAt(left) == A.charAt(right)) {//坐标合法
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
            //为偶数的情况
            right = i + 1;
            left = i;
            while (left >= 0 && right < n && A.charAt(left) == A.charAt(right)) {//坐标合法
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
        }
        return ret;
    }

    public void mainLongLow(String[] args) {
        System.out.println(getLongestPalindrome("qwerarew1WW1qqqwwweeewwwqqq1WW1"));
    }

    public int getLongestPalindrome(String A) {
        if (A.length() == 1) {
            return 1;
        }
        int ret = 0;
        //从右向左
        int n = A.length();
        int j = 0;
        for (int i = 1; i < n; i++) {
            int tmpL = 0;
            int ii = i;
            int jj = j;
            boolean mid = false;//中间是否隔了一个字符
            while (i < n && j >= 0 && A.charAt(i) == A.charAt(j)) {//相同了就往回走
                tmpL += 2;
                i++;
                j--;
            }
            //复原
            i = ii;
            j = jj;
            ret = Math.max(tmpL, ret);
            tmpL = 0;
            if (i + 1 < n && j >= 0 && A.charAt(i + 1) == A.charAt(j)) {//隔了一个字符串
                tmpL++;
            }
            while (i + 1 < n && j >= 0 &&
                    A.charAt(i + 1) == A.charAt(j)) {//相同了就往回走,这是中间有隔着的一个字符
                tmpL += 2;
                i++;
                j--;
            }
            ret = Math.max(tmpL, ret);
            //不同走到下一步
            i = ii;
            j = i;
        }
        return ret;
    }

    //day 9

    /**
     * 扑克牌排序
     */
    public boolean IsContinuous(int[] numbers) {
        Arrays.sort(numbers);
        List<Integer> list = new ArrayList<>();
        int count = 0;//0的数量
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] == 0) {
                count++;
            } else {
                int sub = numbers[i + 1] - numbers[i] - 1;
                if (sub < 0) {
                    return false;
                }
                count -= sub;
                if (count < 0) {
                    return false;
                }

            }
        }
        return true;
    }

    public void mainPoke(String[] args) {
        while (true) {
            int[] arr = new int[5];
            Scanner in = new Scanner(System.in);
            for (int i = 0; i < 5; i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(IsContinuous(arr));
        }
    }

    /**
     * 青蛙跳台阶
     * 一次可以条一个或俩个，问有多少种跳法
     *
     * @param args
     */
    public void mainStep(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(getMethods(n));
    }

    private int getMethods(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }
        return getMethods(n - 1) + getMethods(n - 2);
    }

    //给字符串加逗号
    public void mainLow(String[] args) {
        Scanner in = new Scanner(System.in);
        int val = in.nextInt();
        String s = val + "";
        List<Character> list = new ArrayList<>();
        for (char c : s.toCharArray()) {
            list.add(c);
        }
        int three = 3;
        for (int i = list.size() - 1; i >= 0; i--) {
            three--;
            while (three == 0) {
                list.add(i, ',');
//                i++;
//                i--;
                three = 3;
            }
        }
        if (list.get(0) == ',') {
            list.remove(0);
        }
        for (Object c : list.toArray()) {
            System.out.print(c);
        }
//        System.out.println("stop");
    }


    /**
     * 天星期三全是课
     *
     * @param args
     */
    public void mainThree(String[] args) {
        System.out.println("全是课全是课");
    }

    /**
     * 字母搜集 广度优先
     * 每次可以向右走或者向下走
     * l=4,o=3,v=2,e=1
     * 超时了www 能用
     * 动态规划解决
     */
    //动态规划 dp[i][j]这位置表示的是到这里的到的最高分 就是是
    //dp[i][j] = max(dp[i-1][j],dp[i][j-1])+curMark val数组初始化 额外加一行和列 避免越界的行为
    public void mainFindC(String[] args) {
        Scanner in = new Scanner(System.in);
        int y = in.nextInt();
        int x = in.nextInt();
        String[] chars = new String[y];
        in.nextLine();
        char[][] chars1 = new char[y][x];
        for (int i = 0; i < y; i++) {
            chars[i] = in.nextLine();
        }
        for (int i = 0; i < y; i++) {
            chars1[i] = chars[i].toCharArray();
        }
        int[][] vals = new int[y + 1][x + 1];

        System.out.println("stop");
        getMaxMarkII(chars1, vals);
        System.out.println(vals[y][x]);
    }

    private void getMaxMarkII(char[][] chars, int[][] vals) {
        for (int i = 1; i < vals.length; i++) {//y
            for (int j = 1; j < vals[0].length; j++) {//x
                //得到当前的字符的值
                int mark = getCurM(chars, j - 1, i - 1);
                mark += Math.max(vals[i - 1][j], vals[i][j - 1]);
                vals[i][j] = mark;
            }
        }
    }

    int getCurM(char[][] chars, int x, int y) {
        int mark = 0;
        if (chars[y][x] == 'l') {
            mark += 4;
        } else if (chars[y][x] == 'o') {
            mark += 3;
        } else if (chars[y][x] == 'v') {
            mark += 2;
        } else if (chars[y][x] == 'e') {
            mark += 1;
        }
        return mark;
    }
//       int m, n;//x,y

    public void mainFind(String[] args) {
        Scanner in = new Scanner(System.in);
        int y = in.nextInt(), x = in.nextInt();
        m = x;
        n = y;
        String[] chars = new String[y];
        in.nextLine();
        for (int i = 0; i < y; i++) {
            chars[i] = in.nextLine();
        }
        char[][] chars1 = new char[y][x];
        for (int i = 0; i < y; i++) {
            chars1[i] = chars[i].toCharArray();
        }
        long start = System.currentTimeMillis();
        int mark = getMaxMark(chars1, 0, 0);
        long end = System.currentTimeMillis();
        System.out.println(mark);
        System.out.println(end - start);
    }

    //先右边走和下边走
    int[] dx1 = {1, 0};
    int[] dy1 = {0, 1};

    private int getMaxMark(char[][] chars, int x, int y) {
        if (x >= m || y >= n) {//坐标合法
            return 0;
        }
        if (chars[y][x] == 'l') {//判断相加的分数
            return Math.max(getMaxMark(chars, x + dx1[0], y + dy1[0]), getMaxMark(chars, x + dx1[1], y + dy1[1])) + 4;
        } else if (chars[y][x] == 'o') {
            return Math.max(getMaxMark(chars, x + dx1[0], y + dy1[0]), getMaxMark(chars, x + dx1[1], y + dy1[1])) + 3;
        } else if (chars[y][x] == 'v') {
            return Math.max(getMaxMark(chars, x + dx1[0], y + dy1[0]), getMaxMark(chars, x + dx1[1], y + dy1[1])) + 2;
        } else if (chars[y][x] == 'e') {
            return Math.max(getMaxMark(chars, x + dx1[0], y + dy1[0]), getMaxMark(chars, x + dx1[1], y + dy1[1])) + 1;
        } else {
            return Math.max(getMaxMark(chars, x + dx1[0], y + dy1[0]), getMaxMark(chars, x + dx1[1], y + dy1[1]));
        }
    }

    /**
     * 最长的连续子序列
     *
     * @param arr
     * @return
     */
    public int MLS(int[] arr) {
        int max = 0;
        Set<Integer> set = new HashSet<>();
        for (int i : arr) {
            set.add(i);
        }
        for (int i : set) {
            int tmpMax = 1;
            while (set.contains(i + 1)) {
                tmpMax += 1;
                i = i + 1;
            }
            max = Math.max(max, tmpMax);
        }
        return max;
    }

    public void mainMLs(String[] args) {
        mainRun m = new mainRun();
        int[] arr = {100, 4, 200, 1, 3, 2};
        m.MLS(arr);
    }

    /**
     * 求俩数的最小公倍数
     *
     * @param args
     */
    public void mainMultiple(String[] args) {
        Scanner in = new Scanner(System.in);
        long a1 = in.nextLong();
        long a2 = in.nextLong();
        int i = 1, j = 1;
        while (a1 != a2) {
            if (a1 * i < a2 * j) {
                i++;
            } else if (a1 * i > a2 * j) {
                j++;
            } else {//相同
                break;
            }
        }
        System.out.println(a1 * i);
    }

    /**
     * 能否构成三角形
     *
     * @param args
     */
    public void mainTriangle(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][6];
        for (int i = 0; i < n; i++) {
            //获得数字
            for (int j = 0; j < 6; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            if (isTriangle(arr[i])) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    boolean isTriangle(int[] arr) {
        //判断能否构成三角形 暴力
        for (int j = 0; j < 6; j++) {
            //使用哈希记录下构成三角形的下标
            Set<Integer> set = new HashSet<>();
            for (int k = 0; k < 6; k++) {
                set.add(k);
            }
            //判断
            for (int k = j + 1; k < 6; k++) {
                int sum = arr[j] + arr[k];//俩边和
                int sub = arr[j] - arr[k];//俩边差
                for (int l = k + 1; l < 6; l++) {
                    if (sum > arr[l] && sub < arr[l]) {
                        //这个三角形能构成 判断剩下的能不能构成三角形
                        set.remove(j);
                        set.remove(k);
                        set.remove(l);
                        int[] t1 = new int[3];
                        int index = 0;
                        for (int i : set) {
                            t1[index++] = i;
                        }
                        int sum2 = t1[0] + t1[1];
                        int sub2 = t1[1] - t1[0];
                        if (sum2 > t1[2] && sub2 < t1[2]) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    /**
     * 岛屿的数量
     *
     * @param args
     */
    public void mainLAND(String[] args) {
        char[][] grid = {{'1', '1', '0', '0', '0'}, {'0', '1', '0', '1', '1'}
                , {'0', '0', '0', '1', '1'}, {'0', '0', '0', '0', '0'}, {'0', '0', '1', '1', '1'}};
        mainRun m = new mainRun();
        System.out.println(m.solve(grid));
    }

    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int Y = 0, X = 0;

    public int solve(char[][] grid) {
        int count = 0;
        Y = grid.length;
        X = grid[0].length;
        boolean[][] used = new boolean[Y][X];//使用过就个置为true
        for (int i = 0; i < Y; i++) {
            for (int j = 0; j < X; j++) {
                if (grid[i][j] == '1' && !used[i][j]) {
                    used[i][j] = true;
                    run(grid, used, j, i);//递归遍历所有挨着的为1的岛屿，将他们的used更改
                    //但是这些岛屿只是算是一个岛
                    count++;
                }
            }
        }
        return count;
    }

    void run(char[][] grid, boolean[][] used, int x, int y) {
        //遍历周围
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < X && xx >= 0 && yy < Y && yy >= 0
                    && grid[yy][xx] == '1' && !used[yy][xx]) {
                used[yy][xx] = true;
                run(grid, used, xx, yy);
            }
        }
    }

    /**
     * 得到字符串最长的的字符数组
     *
     * @param args
     */
    public void mainLand(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < n; i++) {
            StringBuilder tmp = new StringBuilder();
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {//是数字
                tmp.append(s.charAt(i));
                for (int j = i + 1; j < n; j++) {
                    if (s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                        tmp.append(s.charAt(j));
                    } else {
                        break;
                    }
                }
            }
            if (ret.length() < tmp.length()) {
                ret = tmp;
            }
        }
        System.out.println(ret.toString());
    }


    //likou

    public int[] minBitwiseArray(List<Integer> nums) {
        int[] ans = new int[nums.size()];
        Arrays.fill(ans, -1);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j <= nums.get(i); j++) {
                if ((j | (j + 1)) == nums.get(i)) {
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }

    public void main12(String[] args) {
        int[] arr = {2, 3, 5, 7};
        List<Integer> list = new ArrayList<>();

        list.add(41);
        mainRun.minBitwiseArrayBe(list);
    }

    /**
     * 斯特林数 x|(x+1)=x
     * 为偶数的话就不存在这个数，而为基数的话一定存在这个数
     * 其实就是吧二进位最右边的0变为1然后的到的最终的数就是nums储存的数
     * 那么要算的就是得到将最右边的1变为0后得到的数
     * 10(1)111 -- 10(0)111 | 101000 = 101111
     * 若为偶数的话，他的第一为为0，而要算的数的是一位无论如何都为1的，所以为偶数不存在
     */
    public static int[] minBitwiseArrayBe(List<Integer> nums) {
        int[] ans = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                ans[i] = -1;
            } else {
                int tmp = ~nums.get(i);
                tmp = tmp & -tmp;
                ans[i] = (tmp >> 1) ^ nums.get(i);
            }
        }
        return ans;
    }

    public void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int times = in.nextInt();
        int[][] arr = new int[times][3];
        for (int i = 0; i < times; i++) {//储存在一个二维数组中
            for (int j = 0; j < 3; j++) {
                arr[i][j] = in.nextInt();
            }
        }
        for (int i = 0; i < times; i++) {
            int mark = 0;
            if (arr[i][0] >= 1 && arr[i][1] >= 1 && arr[i][2] >= 1) {
                int min = Math.min(Math.min(arr[i][0], arr[i][1]), arr[i][2]);
                mark = 2 * min;
                if (arr[i][0] == min) {
                    arr[i][0] -= min;
                    arr[i][1] -= min;
                } else if (arr[i][1] == min) {
                    arr[i][1] -= min;
                    arr[i][1] -= min;
                } else {
                    arr[i][2] -= min;
                    arr[i][1] -= min;
                }
            }
            if (arr[i][1] >= 2) {
                mark += arr[i][1] - 1;
            }
            System.out.println(mark);
        }
    }

    public void mai0n2(String[] args) {
        text t = new text();
        ArrayList<ArrayList<Integer>> grid = crateList();
        System.out.println(t.rotApple(grid));
        System.out.println("stop");
    }

    ArrayList<ArrayList<Integer>> crateList() {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> l1 = new ArrayList<>();
        l1.add(2);
        l1.add(1);
        l1.add(0);
        ArrayList<Integer> l2 = new ArrayList<>();
        l2.add(1);
        l2.add(0);
        l2.add(1);
        ArrayList<Integer> l3 = new ArrayList<>();
        l3.add(0);
        l3.add(0);
        l3.add(0);
        ret.add(l1);
        ret.add(l2);
        ret.add(l3);
        return ret;
    }

    /**
     * 约瑟夫环
     */
    public void mai2n(String[] args) {
        LastRemaining_Solution(1, 3);
    }

    //动态规划
    public int LastRemaining_Solution(int n, int m) {
        int f = 0;
        int ret = 0;
        for (int i = 2; i <= n; i++) {//循环n-1次
            ret = (f + m) % i;//ret为在有i给元素时，该游戏的胜利者
            f = ret;//f时在i-1个元素时，游戏的胜利者
        }
        return ret;
    }

    //模拟
    public void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int size = n;
        int[] arr = new int[n];
        int index = 0;
        for (int i = 1; ; i++) {
            while (arr[index % arr.length] == -1) {
                //这个下标下的已经退出了游戏
                index++;
            }
            if (i % m == 0) {//表明这个位置的孩子要退出游戏
                arr[index % arr.length] = -1;
                size--;
            }
            if (size == 1) {
                break;
            }
            index++;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != -1) {
                System.out.println(i);
                break;
            }
        }
    }

    List<List<Integer>> creat() {
        List<List<Integer>> l = new ArrayList<>();
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        List<Integer> l3 = new ArrayList<>();
        List<Integer> l4 = new ArrayList<>();
        List<Integer> l5 = new ArrayList<>();
        l1.add(1);
        l1.add(0);
        l1.add(1);
        l1.add(1);
//         l1.add(0);
//         l1.add(0);
//         l1.add(0);
//         l1.add(1);
//         l1.add(1);
//         l1.add(1);
//         l1.add(1);
//         l1.add(0);
//         l1.add(0);
//         l1.add(0);
//         l1.add(1);
//         l1.add(1);
//         l1.add(0);
//         l1.add(0);
//         l1.add(0);

        l2.add(0);
        l2.add(0);
        l2.add(0);
        l2.add(1);
//         l2.add(0);
//         l2.add(1);
//         l2.add(0);
//         l2.add(0);
//         l2.add(0);
//         l2.add(0);
//         l2.add(0);

        l3.add(1);
        l3.add(0);
        l3.add(1);
        l3.add(1);
//         l3.add(1);
//         l3.add(0);
//         l3.add(1);
//         l3.add(0);
//         l3.add(1);
//         l3.add(1);
//         l3.add(0);
//         l3.add(1);

        l4.add(0);
        l4.add(1);
        l4.add(1);
        l4.add(0);
//         l4.add(0);
//         l4.add(0);
//         l4.add(1);
//         l4.add(0);

        l5.add(1);
        l5.add(0);
        l5.add(0);
        l5.add(1);

        l.add(l1);
        l.add(l2);
        l.add(l3);
        l.add(l4);
        l.add(l5);
        return l;
    }


    public void main11(String[] args) {
        text t = new text();

        List<List<Integer>> l = creat();
        System.out.println(t.findSafeWalk(l, 4));
    }
}

public class text {
    //穿越网格的安全路径
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    boolean[][] walked;//走过的为true
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        walked = new boolean[grid.size()][grid.get(0).size()];
        if (grid.get(0).get(0) == 1) {
            health--;
        }
        return isTrue(grid, health, 0, 0);
    }

    private boolean isTrue(List<List<Integer>> grid, int health, int x, int y) {
        walked[y][x] = true;
        if (x == grid.get(0).size() - 1 && y == grid.size() - 1 &&
                walked[grid.size() - 1][grid.get(0).size() - 1] && health > 0 || health > grid.size() + grid.get(0).size()) {
            return true;
        }
        for (int i = 0; i < 4 && health>0; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < grid.get(0).size() && yy >= 0 && yy < grid.size() &&
                    grid.get(yy).get(xx) == 0 && !walked[yy][xx]) {
                if (isTrue(grid, health, xx, yy)) {
                    return true;
                }
            }
        }
        //往一走 掉健康值
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < grid.get(0).size() && yy >= 0 && yy < grid.size() &&
                    grid.get(yy).get(xx) == 1 && health > 0) {
                 if (isTrue(grid, health-1, xx, yy)) {
                    return true;
                }

            }
        }
        walked[y][x] = false;
        return false;
//        if (x + 1 < grid.get(0).size() && y < grid.size() && health > 0&& !walked[y][x+1]) {
//            掉健康值往右边走
//            if (isTrue(grid, --health, x + 1, y)) {
//                return true;
//            }
//        } else if (x < grid.get(0).size() && y + 1 < grid.size() && health > 0&& !walked[y+1][x]) {
//            掉健康值往下边走
//            if (isTrue(grid, --health, x, y + 1)) {
//                return true;
//            }
//        }
//        walked[y][x] = false;//这条路走不通 回退，并当作没来过
    }

    /**
     * 腐烂的苹果
     * 广度优先搜索BFS  + queue
     * 多源BFS使用queue进行多源的操作
     */
    //上下左右循环
//    int[] dx = {0, 0, 1, -1};
//    int[] dy = {1, -1, 0, 0};
    public int rotApple(ArrayList<ArrayList<Integer>> grid) {
        //先找到所有的腐烂的苹果 储存的是他们对应的下标
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(0).size(); j++) {
                if (grid.get(i).get(j) == 2) {
                    queue.add(new int[]{i, j});//y,x
                }
            }
        }
        int ret = getTime(grid, queue, queue.size());
        for (int i = 0; i < grid.size(); i++) {//遍历一次看是否还有没腐烂的苹果
            for (int j = 0; j < grid.get(0).size(); j++) {
                if (grid.get(i).get(j) == 1) {
                    return -1;
                }
            }
        }
        return ret;
    }

    int getTime(ArrayList<ArrayList<Integer>> grid, Queue<int[]> queue, int size) {
        for (int i = 0; i < size; i++) {//将周围的苹果全部变为腐烂的
            int[] add = queue.poll();//获得对应y,x
            for (int j = 0; j < 4; j++) {
                int x = add[1] + dx[j];
                int y = add[0] + dy[j];
                if (x >= 0 && y >= 0 && y < grid.size() && x < grid.get(0).size()
                        && grid.get(y).get(x) == 1) {//有苹果
                    //将该处加1 记为腐烂的
                    int set = grid.get(y).get(x) + 1;
                    grid.get(y).set(x, set);
                    //加入该点的坐标
                    queue.add(new int[]{y, x});
                }
            }
        }
        if (queue.isEmpty()) {//直到了queue为空 说明表里面没有为1的值了
            return 0;
        }
        return getTime(grid, queue, queue.size())+1;//继续向下递归
    }

    //可以使用kmp
    public int strStrKMP(String haystack, String needle) {
        return 0;
    }

    public int strStr(String haystack, String needle) {
        //枚举
        for (int i = 0; i < haystack.length(); i++) {
            int ret = 0;
            boolean flag = true;
            if (haystack.charAt(i) == needle.charAt(ret)) {
                int index = i;
                for (int j = ret; j < needle.length(); j++) {
                    if (index ==haystack.length()||needle.charAt(j) != haystack.charAt(index++)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return i;
                }
            }
        }
        return -1;
    }

    public    void mai1n(String[] args) {
        String s = "   fly me   to   the moon  ";
        System.out.println(lengthOfLastWord(s));
    }

    //找到俩个最近的距离 可以使用o
    public    void main11(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int length = in.nextInt();
        in.nextLine();
        String[] s = in.nextLine().split(" ");
        String str1 = s[0];
        String str2 = s[1];
        int prev1 = -1;//记录str1的位置
        int prev2 = -1;//记录str2的位置
        int count = Integer.MAX_VALUE;
        for (int i = 0; i < length; i++) {
            String curS = in.nextLine();
            if (curS .equals(str1)) {
                prev1 = i;
                if (prev2 != -1) {
                    count =  Math.min(Math.abs(prev1 - prev2),count);
                }
            }else if (curS .equals(str2)) {
                prev2 = i;
                if (prev1 != -1) {
                    count = Math.min(Math.abs(prev1 - prev2),count);
                }
            }
        }
        System.out.println(count == Integer.MAX_VALUE? -1:count);
    }

    public    void main22(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别 找到区间最小的大于x的数 暴力解法
        int n = in.nextInt();
        int x = in.nextInt();
        int[] arr = new int[n];
        int user = 0;
        int[] length = new int[n];//储存每个下标下的
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        for (int i = 0; i < n; i++) {
            int j = i;
            int tmpSum = 0;
            boolean flg = false;
            for (; j < n; j++) {//在这里面找到比n大的
                tmpSum += arr[j];
                if (tmpSum >= x) {
                    flg = true;
                    break;
                }
            }
            if (flg) {//说明有解
                length[i] = j;
                user++;
            }
        }
        int left = 0xf3f3f3f3;
        int right = 0xfffffff;
        int min = length[0];
        for (int i = 1; i < user; i++) {
            if (length[i] - i < min) {
                min = length[i] - i;
                left = i;
                right = length[i];
            }
        }
        System.out.println(left +" "+right);
    }
    // 每次/2除到最小
    public    void mai12n(String[] args) {
        //建立一个大根堆 每次储存的都是偶数 每次都是出堆顶的并如果后来的数是偶数，那么就继续插入对里面
        PriorityQueue<Integer> stack = new PriorityQueue<>((a,b)->b-a);//大根堆
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//对应的数据个数
        int k = in.nextInt();
        long sum = 0;
        for (int i = 0; i < n; i++) {
            int tmp = in.nextInt();
            sum += tmp;
            if (tmp % 2 == 0) {
                stack.add(tmp);
            }
        }
        for (int i = 0; i < k; i++) {
            if (!stack.isEmpty()) {
                int tmp = stack.poll();

                sum -= tmp;
                tmp /= 2;
                sum += tmp;

                if (tmp % 2 == 0) {
                    stack.add(tmp);
                }
            }
        }
        System.out.println(sum);
    }

    public    void main12(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        long sum = 0;
        int[] arr = new int[n];
        //每次找到最大的
        for (int i = 0; i < n; i++) {
            int tmp = in.nextInt();
            arr[i] = tmp;
            sum += tmp;
        }
        for (int i = 0; i < k; i++) {
            Arrays.sort(arr);
            int index = arr.length - 1;
            for (; index >=0 ; index--) {
                if (arr[index] % 2 == 0) {
                    break;
                }
            }
            sum -= arr[index];
            arr[index] /= 2;
            sum += arr[index];
        }
        System.out.println(sum);
    }
    public    void main111(String[] args) {
        Scanner in = new Scanner(System.in);

        String[] strs = in.nextLine().split(" ");

        StringBuffer ret = new StringBuffer();

        for (String s : strs) {
            ret.append(Character.toUpperCase(s.charAt(0)));
        }
        System.out.println(ret.toString());
    }

    //Fibonacci 计算第n项 0 1 1 2 3 5 8 13 21 34
    //                  p c
    public    String fibonacci(int n) {

        if (n == 1) {
            return 0+"";
        }
        if (n == 2) {
            return 1 + "";
        }
        String prev = 0+"";
        String cur = 1+"";
        String sum = 0+"";
        for (int i = 0; i < n; i++) {
            sum = solveRoot(prev+"", cur + "");
            prev = cur;
            cur = sum;
        }
        return sum+"";
    }

    public    void main(String[] args) {
        System.out.print(fibonacci(99));
    }
    public    void mainn(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        System.out.println(fib(x));
    }
       int fib(int x){
        int tmp = x;
        if(tmp == 0||tmp==1){
            return tmp;
        }
        int prev1 = 0;
        int prev2 = 1;
        while(true){//
            int cur = prev1+prev2;
            //走到下一个去计算
            prev1 = prev2;
            prev2 =cur;
            int flg1 = cur-x;
            if(flg1<=0) {
                //在计算一次 算的是他的下一个
                int tmpVal = prev1 + prev2;
                int flg2 = tmpVal - x;
                if (flg1 <= 0 && flg2 >= 0) {
                    return Math.min(Math.abs(flg2), Math.abs(flg1));
                }
            }
        }
    }

    public    void main1111(String[] args) {
        Random r = new Random();
        int a = r.nextInt(0,2);
        boolean[][] tmp = new boolean[2][2];
        System.out.println("stop");

    }
    public boolean exist1 (String[] board, String word) {
        // write code here
        //前后加个空格 这样就可以避免越界
        for (int i = 0; i < board.length; i++) {
            board[i] = " " + board[i] + " ";
        }

        Random r = new Random();
        int a = r.nextInt(0,2);

        return find(board, word);
    }

    public    void main234(String[] args) {
        String[] s = {"XYZE", "SFZS", "XDEE"};
        String[] s1 = {"X"};
        text t = new text();
//        System.out.println(t.exist(s1, "X"));
        System.out.println(t.exist(s, "XYZZED"));
    }
    int m, n;//是数组长度y x
    boolean[][] vil;//用来记录走过的路
    public  boolean exist (String[] board, String word) {
        //
        m = board.length;
        n = board[0].length();
        vil = new boolean[m][n];
        for (int i = 0; i < m; i++) {//i->y
            for (int j = 0; j < n; j++) {//j->x
                if (board[i].charAt(j) == word.charAt(0)) {
                    if (dfs(board, word, j, i, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //定义俩数组 用来遍历周围元素
    int[] xx = {-1, 1, 0, 0};
    int[] yy = {0, 0, -1, 1};
    private boolean dfs(String[] board, String word, int j, int i, int index) {
        if (index == word.length() - 1) {
            return true;
        }
        vil[i][j] = true;//表示这里走过了
        for (int k = 0; k < 4; k++) {
            int x = j + xx[k];
            int y = i + yy[k];
            //每次都是找到的index的下一个 因为第一个已经是相同的才会进入这个循环的 然后接着走到word的下一然后继续这样比较
            if (x >= 0 && x < n && y >= 0 && y < m && !vil[y][x] && board[y].charAt(x) == word.charAt(index+1)) {
                if(dfs(board, word, x, y, index+1)){//表示的是若没找到但是还是要继续循环的 而不是直接退出
                    return true;
                }
            }
        }
        vil[i][j] = false;//全部循环了没找到相同的没找到相同的那就还为false
        return false;
    }

       boolean find(String[] board, String word) {
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length(); x++) {

            }
        }
        return true;
    }

    public    void main23(String[] args) {
        creatTriangle(6);
    }
       void creatTriangle(int deep){
        if (deep == 1) {
            System.out.printf("%5d\n",1);
            return;
        }
        //大于1称高度
        System.out.printf("%5d\n",1);
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        for (int i = 2; i <= deep; i++) {
            //每层高度的个数和高度相同只需要计算中间的数
            List<Integer> tmp = new ArrayList<>();
            tmp.add(1);
            tmp.add(1);
            for (int j = 1; j < i - 1; j++) {
                int val = list.get(j - 1) + list.get(j);
                tmp.add(j, val);
            }
            //打印
            for (int j = 0; j < tmp.size(); j++) {
                System.out.printf("%5d",tmp.get(j));
            }
            System.out.println();
            list = tmp;
        }

    }
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
        public   void main1(String[] args) {
            Scanner in = new Scanner(System.in);
            // 注意 hasNext 和 hasNextLine 的区别
            int length = in.nextInt();
            in.nextLine();
            String strs = in.nextLine();
            String strs1 = strs.substring(0,strs.indexOf(" "));
            String strs2 = strs.substring(strs.indexOf(" ")+1);
            if(length <= 1 || strs1 == null || strs2 == null){
                System.out.print(-1);
                return;
            }
            boolean isHave = false;
            int minLength = Integer.MAX_VALUE;
            int curLength = 0;
            String[] ss = new String[length];
            for (int i = 0; i < length; i++) {
                ss[i] = in.nextLine();
            }

            for(int i = 0 ; i < length;){//遍历字符串数组
                String tmp = ss[i];

                if(tmp.equals(strs1)){//那么接下来就要找的是tmp = QWER 找 str2 666
                    curLength = 0;
                    isHave = false;
                    for(int j = i; j < length;j++){
                        String tmp2 = ss[j];
                        if(tmp2.equals(strs2)){//666
                            isHave = true;
                            tmp = tmp2;
                            i = j;
                            break;
                        }
                        curLength++;
                    }
                }
                if(!isHave && curLength != Integer.MAX_VALUE){
                    minLength = -1;
                }
                if(curLength < minLength){
                    minLength = curLength;
                }

                if(tmp.equals(strs2)){//tmp = 666 那么接下来就要找的是str1 QWER
                    isHave = false;
                    curLength = 0;
                    for(int j = i; j < length;j++){
                        String tmp1 = ss[j];
                        if(tmp1.equals(strs1)){//strs1 QWER
                            isHave = true;
                            tmp = tmp1;
                            i = j;
                            break;
                        }
                        curLength++;
                    }
                }

                if(!isHave && curLength != Integer.MAX_VALUE){
                    minLength = -1;
                }
                if(curLength < minLength){
                    minLength = curLength;
                }
                if(!tmp.equals(strs1) && !tmp.equals(strs2)){
                    i++;
                }
            }
            System.out.print(minLength);
        }
        //最小花费爬楼梯 楼顶是数组的最后一个元素的下一个

    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        //dp记录的是到该位置的最小的花费
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
        }
        return dp[cost.length];
    }

    //最后一个单词的长度
    public   int lengthOfLastWord(String s) {
        StringBuffer s1 = new StringBuffer(s);
        int count = 0;
        boolean flg = false;
        int end = 0;
        for (int i = s1.length()-1; i > 0; i--) {
            if (s1.charAt(i) == ' ') {
                if (flg) {
                    break;
                }
                continue;
            }
            count++;
            flg = true;
        }
        return count;
    }

    public   ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curPrev = null;
        ListNode curNext = cur.next;
        if (curNext == null) {
            return head;
        }
        while (curNext != null) {
            ListNode tmp = curNext.next;
            if (curPrev == null) {
                curNext.next = cur;
                cur.next = tmp;
                head = curNext;
            } else {
                curNext.next = cur;
                cur.next = tmp;
                curPrev.next = curNext;
            }
            curPrev = cur;
            cur = cur.next;
            if (cur == null) {
                break;
            }
            curNext = cur.next;
        }
        return head;
    }

    public    void main8(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for (int i = 2; i < 2; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        head =swapPairs(null);
        System.out.println("stop");
    }

    public   void main112(String[] args) {
        int[] arr = {6,6,6,3,2,6,5};
        int[] arr1  = {3,2,4,3};
//        minElement(arr);
        System.out.println(maximumTotalSum(arr1));
    }

    public   long maximumTotalSum(int[] maximumHeight) {
        //使用set记录每次设置的高度有了往下减一一直到没有
        Arrays.sort(maximumHeight);
        int prev = maximumHeight[maximumHeight.length - 1];
        long ret = prev;
//        Set<Integer> have = new HashSet<>();
        //
        for (int i = maximumHeight.length - 2; i >= 0; i--) {
            if (maximumHeight[i] < prev) {
                ret += maximumHeight[i];
                prev = maximumHeight[i];
            } else if (maximumHeight[i] == prev) {
                int tmp = 1;
                while (i >=0&&maximumHeight[i] == prev) {
                    ret = ret + prev - tmp;
                    tmp++;
                    i--;
                }
                prev = maximumHeight[++i]-tmp;//这是最后不相同的
            }
            if (prev <= 0) {
                return -1;
            }
        }
        return ret;

    }

    public int[] validSequence(String word1, String word2) {
        Map<Character, Integer> map1 = new HashMap<>();
        for (int i = 0; i < word1.length(); i++) {
            map1.put(word1.charAt(i), i);
        }
        char[] chars = word2.toCharArray();
        int[] ret = new int[word2.length()];
        int index = 0;
        for (int i =0;i < chars.length;i++) {
            if (map1.containsKey(chars[i])) {
                ret[index++] = map1.get(chars[i]);
            }
        }

        return index == chars.length ? ret : null;
    }


    public   void mainbigNum(String[] args) {
//        "733064366","459309139"
        System.out.println(solve("459309139", "733064366"));
    }
    //大数乘法
    public   String solve (String s, String t) {
//        "336703162779040874"
        //使用俩层for循环，先不进为，吧数相加后储存在数组中，然后在左处理
        if (s.charAt(0) - '0' == 0 || t.charAt(0) - '0' == 0) {
            return "0";
        }//733064366","459309139"
        StringBuffer ss = new StringBuffer(s).reverse();
        StringBuffer tt = new StringBuffer(t).reverse();
        int[] arr = new int[s.length() + t.length()-1];
        for (int i = 0; i < ss.length(); i++) {
            for (int j = 0; j < tt.length();  j++) {
                arr[i + j] += (ss.charAt(i) - '0') * (tt.charAt(j) - '0');
            }
        }
        //处理进位
        StringBuffer ret = new StringBuffer();
        int plus = 0;
        for (int i = 0; i < arr.length; i++) {
            plus += arr[i];
            ret.append(plus % 10);
            plus /= 10;
        }
        while (plus != 0) {
            ret.append(plus % 10);
            plus /= 10;
        }
        return ret.reverse().toString();
    }

    public   void maiwqn(String[] args) {
//        System.out.println(solve("111", "9999"));
        System.out.println(solve1("11", "0"));
    }
    public   String solve1 (String s, String t) {
        // write code here
        if (s.length() < t.length()) {//s长度小
            String ret = "0";
            int times = toInt(s);
            for (int i = 0; i < times; i++) {
                ret = solveRoot(t, ret);
            }
            return ret;
        } else {//s长度长
            String ret = "0";
            int times = toInt(t);
            for (int i = 0; i < times; i++) {
                ret = solveRoot(s, ret);//加上s t次
            }
            return ret;
        }
    }

    private   int toInt(String s) {
        int ret = 0;
        int plus = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (plus == 0) {
                ret += (s.charAt(i) - '0');
                plus++;
            } else {
                int tmp = s.charAt(i) - '0';
                for (int j = 0; j < plus; j++) {
                    tmp *= 10;
                }
                ret += tmp;
                plus++;
            }
        }
        return ret;
    }


    /**
     *  126
     *  234
     *     063
     *     360
     *   123
     *   3-'0' -> 3
     */

    //大数加法 模拟加法
    public   String solveRoot (String s, String t) {
        // write code here
        StringBuffer ret = new StringBuffer();
        boolean plus = false;//进制加一 '1' - '0'获得数字
        int sIndex = s.length() - 1;
        int tIndex = t.length() - 1;
        while (sIndex >= 0 || tIndex >= 0) {
            int tmpS = 0;
            int tmpT = 0;
            if (sIndex >= 0) {//获得s在这位的数字
                tmpS = s.charAt(sIndex) - '0';
                sIndex--;
            }
            if (tIndex >= 0) {//获得t在这位的数字
                tmpT = t.charAt(tIndex) - '0';
                tIndex--;
            }

            int sum = 0;
            if (plus) {//要进位
                sum += 1;
                plus = false;
            }
            sum =sum+ tmpS + tmpT;//获得该为数相加的值
            if (sum - 10 >= 0) {//要向前进一位
                sum %= 10;
                plus = true;
            }
            ret.append(sum);
        }
        if (plus) {
            ret.append("1");
        }
        ret.reverse();
        return ret.toString();
    }

    public   ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        StringBuffer s = new StringBuffer();
        StringBuffer t = new StringBuffer();
        for (ListNode i = head1; i != null; i = i.next) {
            s.append(i.val);
        }
        for (ListNode i = head2; i != null; i = i.next) {
            t.append(i.val);
        }
        ListNode ret = new ListNode(1);
        ListNode cur = ret;

        String solved = solveRoot(s.toString(), t.toString());
        for (int i = 0; i < solved.length(); i++) {
            cur.next = new ListNode(solved.charAt(i) - '0');
            cur = cur.next;
        }
        return ret;
    }
    public   int minElement(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int n : nums) {
            int sum = 0;
            while (n >= 0) {//10
                sum += n % 10;
                n /= 10;
            }
            min = n;
        }
        return min;

    }


    public   ListNode removeNthFromEnd(ListNode head, int n) {
        Map<Integer, ListNode> map = new HashMap<>();
        int index = 1;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            map.put(index++, cur);
        }
        int delNodeIndex = map.size() - n + 1;//开头为1
        ListNode delPrev = map.getOrDefault(delNodeIndex-1,null);
        ListNode delNext = map.getOrDefault(delNodeIndex+1,null);
        if (delPrev != null) {
            delPrev.next = delNext;
        } else {//为空
            head = delNext;
        }
        return head;
    }

    public ListNode removeNthFromEndBE(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode fast = dummyNode.next,slow = dummyNode;
        for(int i = 0 ; fast != null && i < n ; i++) fast = fast.next;//先走n步
        while(fast != null){//这时才走slow当fast走到了null slow正好为倒数第n个节点
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }

    public   void main7(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for (int i = 2; i <= 5; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        head = removeNthFromEnd(head,5);
        System.out.println("s");
    }


    public   List<List<String>> groupAnagramsDown(String[] strs) {
        List<List<String>> retList = new LinkedList<>();
        List<String> strS = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();

        Collections.addAll(strS, strs);//将strs变为链表

        while (strS.size() != 0) {//循环一次找到一种相似的字符串
            int index = 0;//用来遍历链表 StrS
            List<String> tmpList = new LinkedList<>();//最终插到retList

            //将第一个元素给到tmpList
            String tmpS = strS.get(0);

            tmpList.add(tmpS);
            strS.remove(0);//得到后就删除
            //遍历tmpS放到map中
            for (int i = 0; i < tmpS.length(); i++) {
                if (map.containsKey(tmpS.charAt(i))) {//存在这个K
                    map.put(tmpS.charAt(i), map.get(tmpS.charAt(i)) + 1);
                } else {
                    map.put(tmpS.charAt(i), 1);
                }
            }
            //map中的就是每个字符的个数
            for (int i = 0; i < strS.size(); i++) {//遍历tmpS找到对于的字符串
                Map<Character, Integer> tmpMap = new HashMap<>(map);
                String s = strS.get(i);
                if (s.length() == 0) {//考虑""这个情况
                    if (tmpMap.isEmpty()) {
                        tmpList.add("");
                        strS.remove(i);//插入了就删
                        i--;//这时删除了一个元素，下一个元素也就指向的这个i所指向的地方所以--
                    }
                }else {//剩下的就都不为""
                    //能进入这里说明要找的不为""map也不会为“”
                    boolean flg = true;//可能map本来九尾空
                    if (tmpMap.isEmpty()) {
                        flg = false;//
                    }
                    for (int j = 0; j < s.length(); j++) {//遍历字符串的每个字符
                        if (tmpMap.containsKey(s.charAt(j))) {//如果存在
                            tmpMap.put(s.charAt(j), tmpMap.get(s.charAt(j)) - 1);
                            if (tmpMap.get(s.charAt(j)) == 0) {
                                tmpMap.remove(s.charAt(j));//说明没有这个字符了
                            }
                        } else {//不存在就直接推出
                            if (tmpMap.isEmpty()) {//map空了但是字符串还未空
                                flg = false;
                            }
                            break;
                        }
                    }
                    if (tmpMap.isEmpty() && flg) {//这时说明这个字符串符合，说明tmp刚开始不为空现在为空了
                        tmpList.add(s);
                        strS.remove(i);
                        i--;
                    }
                }
            }
            retList.add(tmpList);
            map.clear();
        }
        return retList;
    }

    public   List<List<String>> groupAnagramsBE(String[] strs) {
        //使用排好序的字符串作为唯一key
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
//            if (map.containsKey(key)) {
//                map.get(key).add(str);
//            } else {
//                map.put(key, new LinkedList<>());
//                map.get(key).add(str);
//            }
            //BE
            List<String> list = map.getOrDefault(key, new LinkedList<>());//存在key就返回对应的list 不存在就new新的并返回
            list.add(str);
            map.put(key, list);
        }
        return new LinkedList<List<String>>(map.values());
    }


    public    void main2(String[] args) {
        String[] s = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> h = groupAnagramsBE(s);
        System.out.println("s");
        HashSet<Integer> hashSet = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        int[] arr = {1, 2,3};
        for (int i:arr) {
            set.add(i);
        }
        for (int i : set) {

        }
    }


    //可以使用for来遍历set中的元素
    public 
    int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int long_max = 0;
        for (int i : set) {
            int curLong = 1;
            if (!set.contains(i - 1)) {//这样这个i就是有序数组的开头元素
                while (set.contains(i+1)) {
                    curLong++;
                    i++;
                }
            }
            long_max = Math.max(curLong, long_max);
        }
        return long_max;
    }

    public boolean isPalindrome(int x) {
        String s = x + "";
        boolean flag = true;
        int start = 0;
        int end = s.length()-1;
        while (end > start) {
            if (s.charAt(start) != s.charAt(end)) {
                flag = false;
                break;
            }
            start++;
            end--;
        }
        return flag;
    }

    //最长公告前缀
    public String longestCommonPrefix(String[] strs) {
        StringBuffer s1 = new StringBuffer();
        for (int index = 0; index < strs[0].length(); index++) {
            char target =  strs[index].charAt(index);
            for (String s : strs) {
                if (index > s.length() || target != s.charAt(index)) {
                    return s1.toString();
                }
            }
            s1.append(target);
            index++;
        }
        return s1.toString();
    }


    public 
    void main6(String[] args) {
        int[] arr = {100, 4, 200, 1, 3, 2, 2};
        longestConsecutive(arr);
    }









    public 
    void main5(String[] args) {
        String[] s = {"eat", "tea", "tan", "ate", "nat", "bat"};
        String[] s1 = {"b", "b","b"};
        String[] s2 = {"", "b"};
        String[] s3 = {"","",""};
        String[] s4 = {"hhhhu","tttti","tttit","hhhuh","hhuhh","tittt"};
        String[] s5 = {"eat", "tea", "tan", "ate", "nat", "bat", "ac", "bd", "aac", "bbd", "aacc", "bbdd", "acc", "bdd"};
        Long start = System.currentTimeMillis();
//        List<List<String>> ss = groupAnagrams(s2);
        Long end = System.currentTimeMillis();
//        ss.size();
        System.out.println("stop");
        System.out.println();
        System.out.println("hhha".hashCode());
        System.out.println("hahh".hashCode());
        System.out.println();
        System.out.println(end - start);

    }

    public    void main3(String[] args) {
        int[] arr1 = {2, 2, 1, 1, 1, 2, 2};
        int[] arr = {2, 3 ,2};
        System.out.println(majorityElement(arr1));
        System.out.println("stop");

    }

    public    int majorityElementBe(int[] nums) {
        int votes = 0;
        int x = 0;
        for (int n : nums) {
            if (votes == 0) {
                x = n;
            }
            votes += (n == x) ? 1 : -1;
        }
        return x;
    }
    public    int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int times = nums.length / 2;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            if (count > times) {
                return nums[i];
            }
        }
        return 0;
    }

    //删除数字
    public String clearDigits(String s) {
        StringBuffer s1 = new StringBuffer(s);
        for (int i = s1.length() - 1; i >= 0; i--) {
            if (Character.isDigit(s1.charAt(i))) {//是数字那就要删除 每删除一个数字就要删除一个字符
                s1.delete(i, i + 1);//包前不包后
                int tmp = i - 1;
                while (Character.isDigit(s1.charAt(tmp))) {//找到数字的下一个字符
                    tmp--;
                }
                if (tmp >= 0) {//说明存在
                    s1.delete(tmp, tmp + 1);
                    i--;
                }
            }
        }
        return s1.toString();
    }
}

class run {
       class Node<E> {
        E val;
        Node<E> left;
        Node<E> right;

        public Node(E val) {
            this.val = val;
        }
    }

    //    public 
    //    void mai1n(String[] args) {
//        text h = new text();
//        System.out.println(h.clearDigits("cb34"));
//    }
    //以之字形打印
    public List<List<Integer>> levelOrder1(Node root) {
        List<List<Integer>> arr = new LinkedList();
        if (root == null) {
            return arr;
        }
        Queue<Node> queue = new LinkedList();
        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tmpL = new LinkedList<>();
            while (size != 0) {
                Node tmp = queue.poll();
                tmpL.add((Integer) tmp.val);
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
                size--;
            }
            //第一层为从左到右
            //第二次为从右到左这样依此下去
            if (flag) {
                Collections.reverse(tmpL);
                flag = false;
            } else {
                flag = true;
            }

            arr.add(tmpL);
        }
//        Collections.reverse(arr);//从下到上打印
        return arr;
    }

    public    void moveZeroes(int[] nums) {
        int length = nums.length;
        int i = 0;
        for (int j = 0; i < length - 1; ) {
            if (nums[i] != 0) {
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
                j++;
            }
            i++;
        }
    }

    public    void moveZeroesBe(int[] arr) {
        int index = 0;
        for (int x : arr) {
            if (x != 0) {
                arr[index++] = x;
            }
        }

        for (int i = index; i < arr.length; i++) {
            arr[i] = 0;
        }
    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new LinkedList<>();
        Set<Integer> hh = new HashSet<>();
        for (int i = 1; i <= nums.length; i++) {
            list.add(i);
        }
        for (int i : nums) {
            if (list.contains(i)) {
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j) == i) {
                        list.remove(j);
                    }
                }
            }
        }
        return list;
    }
    public List<Integer> findDisappearedNumbersBe(int[] nums) {
        //hash//数组置为true
        List<Integer> ret = new LinkedList<>();
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i : nums) {
            hashSet.add(i);

        }
        for (int i = 1; i <= nums.length; i++) {
            if (!hashSet.contains(i)) {
                ret.add(i);
            }
        }
        return ret;
    }
    public    void mainw(String[] args) {
        int[] a = {0, 1, 0, 3, 12};
        int[] b = {0, 0, 1};
        moveZeroesBe(a);
        System.out.println();

    }
}